A layered analysis of consensus

DOI10.1137/S0097539799364006MaRDI QIDQ2784490zbMATH OpenFDO

Authors Yoram Moses, Sergio Rajsbaum

Publication date 23 April 2002

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539799364006

zbMATH Keywords

consensusdistributed systemsimpossibility resultslower boundsshaved-memory systemstopology

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Easy impossibility proofs for distributed consensus problems
• Impossibility of distributed consensus with one faulty process
• Lower bounds for asynchronous consensus
• Synchronous condition-based consensus
• A simple proof of the uniform consensus synchronous lower bound.

Cited in

(35)

• A bivalency proof of the lower bound for uniform consensus
• A simple proof of the uniform consensus synchronous lower bound.
• Layered reasoning for randomized distributed algorithms
• A characterization of oblivious message adversaries for which consensus is solvable
• Synchronous condition-based consensus
• The Heard-Of model: computing in distributed systems with benign faults
• Agreement in synchronous networks with ubiquitous faults
• An axiomatic approach to computing the connectivity of synchronous and asynchronous systems
• A characterization of dynamic networks where consensus is solvable
• Consensus vs. Broadcast in Communication Networks with Arbitrary Mobile Omission Faults
• scientific article; zbMATH DE number 7228882 (Why is no real title available?)
• No Double Discount: Condition-Based Simultaneity Yields Limited Gain
• The topology of distributed adversaries
• Power and limits of distributed computing shared memory models
• No double discount: condition-based simultaneity yields limited gain
• Message and time efficient consensus protocols for synchronous distributed systems
• Consensus in Networks of Multiagents with Stochastically Switching Topologies and Time-Varying Delays
• Tight bounds for adopt-commit objects
• Characterizing Consensus in the Heard-Of Model
• scientific article; zbMATH DE number 7561259 (Why is no real title available?)
• Closed schedulers: a novel technique for analyzing asynchronous protocols
• Hundreds of impossibility results for distributed computing
• The Building Blocks of Consensus
• Synchronous \(t\)-resilient consensus in arbitrary graphs
• The solvability of consensus in iterated models extended with safe-consensus
• Why Extension-Based Proofs Fail
• Reaching consensus in the presence of contention-related crash failures
• Logic of Communication Interpretation: How to Not Get Lost in Translation
• Synchronous t-resilient consensus in arbitrary graphs
• Locally solvable tasks and the limitations of valency arguments
• A speedup theorem for asynchronous computation with applications to consensus and approximate agreement
• Keynote: Time is not a healer: before and after
• Topological characterization of consensus in distributed systems
• Tracking analysis for general linearly coupled dynamical systems
• The complexity of full-information iterated protocols

This page was built for publication: A layered analysis of consensus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2784490)