On processor coordination using asynchronous hardware
Benny Chor, Amos Israeli, Ming Li · 1987
We investigate an asynchronous model of concurrent computations, where processors communicate by shared registers that allow atomic read and write operations (but do not support atomic test-and-set).For this model, we define a general notion of processor coordination, and study the possibility and complexity of achieving coordination.Our definition includes, as special cases, mutual exclusion and asynchronous agreement.It is shown that the coordination problem cannot be solved by means of a deterministic protocol even if the system consists of only two processors.This impossibility result holds for the most powerful type of shared atomic registers and does not assume symmetric protocols.The impossibility result is contrasted by a variety of eficient randomized protocols, that achieve fast coordination for systems of arbitrary number of processors n.These protocols are all fairly simple, constructive, and their ezpectedrun-time is polynomial in n, even in the presence of an adaptive