Can I read The Unified Structure of Consensus: a Layered Analysis Approach on EtoBox?

The Unified Structure of Consensus: a Layered Analysis Approach by Yoram Moses; Sergio Rajsbaum is a scholarly article available to read on EtoBox.

What is The Unified Structure of Consensus: a Layered Analysis Approach about?

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 solvabi

Author

Yoram Moses; Sergio Rajsbaum

Publisher

ACM Press

Published

1998

Language

EN