The unified structure of consensus
Yoram Moses, Sergio Rajsbaum · 1998
We introduce a simple notion of layering that provides a tool for defining submodels of a given model of distributed computation.We describe two layerings, the synchronic and the permutation layering, and show that they induce appropriate submodels of several asynchronous models of computation.The synchronic layering applies to the synchronous model too.We perform a model-independent analysis of the consensus problem in terms of abstract connectivity properties of layering functions.By defining particular layerings in specific models, we derive several popular (and some new) lower bounds and impossibility results for consensus in various classical models.These results are often stronger in the sense that they apply to the subrnodel induced by the layering.The proofs obtained in this way are also simpler and more direct than existing ones.Moreover, the analysis is done in a uniform fashion and demonstrates the fundamental common structure of the consensus problem in the presence of failures.The analysis is then extended to general decision problems (l-resilient in the asynchronous models, t-rounds in the t-resilient synchronous model), providing a characterization of solvability of decision problems in the style of [8] which, for some of the models, is given for the first time.1 introduction For almost two decades now, the consensus problem has played a central role in the study of fault-tolerant distributed computing, e.g.123, 13, 12, 10, 14, 20, 16, 8, 91.It has clearly received the greatest amount of attention in the theoretical literature on distributed computing, and has been studied in a large variety of models and under many types of failure assumptions.Work on different variants often in-*This work has been supported by a Helen and Milton A. Kimmelman career development chair.