In many distributed settings data and resources are shared and there are constraints on their simultaneous access by participating nodes. A fundamental goal in such a setting is to design local distributed contention-resolution protocols so that all the competing nodes can access the shared resources in a coordinated manner. In this presentation, I will discuss the following distributed access problem which naturally arises in many settings: given a set of data items shared among nodes in a distributed network, all nodes want to access all (or a subset of) the items residing on different nodes in a contention-free manner. In addition, in certain applications, items may need to move from one node to the other during access. The goal is to design distributed protocols so that all nodes access all the desired items as quickly as possible, while not overloading the storage space of any one node. In this work, we analyzed a simple and natural, randomized, distributed contention-resolution protocol for the above problem. Our analysis involves a stochastic analysis of a ``balls into bins'' problem in a dynamic setting where balls (data items) move into bins (nodes) on request and we study the time and storage requirements to move all the balls to the requested bins. We obtain almost tight bounds on the performance of the protocol; we show that the protocol performs almost as well as an optimal (centralized) scheme but with no coordination overhead. I will also discuss a few natural applications of our protocol, notably to the problem of computing aggregates in a decentralized manner.
Colloquia Series page.