The ambiguity of choosing
Jeremy Burns, Gary L. Peterson · 1989
In the difficult area of distributed algorithms, it is useful to find tools that have wide application.Here we consider a model in which communication is through asynchronous, atomic reads and writes of shared memory.One of our main results is a lemma showing that a single fail-stop failure can lead to ambiguity whenever a choice must be made.Thii lemma can be used to prove a variety of impossibility results and lower bounds.We use the lemma to give a simple proof of the optimality of our solution to the f-assignment problem.The L-assignment problem requires that a group of processors compete for a pool of distinct resources with the restriction that a limited number of processors can halt unexpectedly.(The problem differs from the normal &exclusion problem in that an explicit assignment of resources must be made.)Use of the lemma is also demonstrated by giving a simple proof for the lower bound of the pure buffers version of the concurrent reading while writing problem.Some other problems where the lemma applies are mentioned.