The Unified Structure of Consensus

The Unified Structure of Consensus: a Layered Analysis Approach

Yoram Moses
Faculty of Electrical Engineering
Technion
Haifa 32000, Israel
moses@ee.technion.ac.il

Sergio Rajsbaum
Instituto de Matemáticas
U.N.A.M.
Mexico City, D.F. 04510, Mexico
rajsbaum@math.unam.mx

Abstract

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 submodel 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 (1-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 [O. Biran, S. Moran and S. Zaks, "Tight Bounds on the Round Complexity of Distributed 1-solvable Tasks," Theoretical Computer Science, Vol. 145 (1995) pp. 271-290], which, for some of the models, is given for the first time.

paper (10 pages), in Proc. 17th ACM Symposium on Principles of Distributed Computing (PODC), p. 133-142, June 1998.