ON CONTENTION RESOLUTION PROTOCOLS AND ASSOCIATED PROBABILISTIC PHENOMENA

Consider an on-line scheduling problem in which a set of abstract proc esses are competing for the use of a number of resources. Further assu me that it is either prohibitively expensive or impossible for any two of the processes to directly communicate with one another. If several processes simultaneously attempt to allocate a particular resource (a s may be expected to occur, since the processes cannot easily coordina te their allocations), then none succeed. In such a framework, it is a challenge to design efficient contention resolution protocols. Two re cently-proposed approaches to the problem of PRAM emulation give rise to scheduling problems of the above kind. In one approach, the resourc es (in this case, the shared memory cells) are duplicated and distribu ted randomly. We analyze a simple and efficient deterministic algorith m for accessing some subset of the duplicated resources. In the other approach, we analyze how quickly we can access the given (nonduplicate d) resource using a simple randomized strategy. We obtain precise boun ds on the performance of both strategies. We anticipate that our resul ts will find other applications.