Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound
From MaRDI portal
Publication:1041222
DOI10.1016/j.tcs.2009.09.002zbMath1189.68021OpenAlexW2085152632MaRDI QIDQ1041222
Corentin Travers, Michel Raynal, Achour Mostefaoui
Publication date: 1 December 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.09.002
Cites Work
- Unnamed Item
- Unnamed Item
- A topological treatment of early-deciding set-agreement
- A bivalency proof of the lower bound for uniform consensus
- A lower bound for the time to assure interactive consistency
- More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
- A simple bivalency proof that \(t\)-resilient consensus requires \(t+1\) rounds
- A simple proof of the uniform consensus synchronous lower bound.
- Tight bounds for \(k\)-set agreement with limited-scope failure detectors
- Synchronous condition-based consensus
- Round-by-round fault detectors (extended abstract)
- Tight bounds for k -set agreement
- The topological structure of asynchronous computability
- Simplifying fault-tolerance
- The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement
- Design and Analysis of Distributed Algorithms
- Conditions on input vectors for consensus solvability in asynchronous distributed systems
- Early stopping in Byzantine agreement
- From a static impossibility to an adaptive lower bound
- Complexity of network synchronization
- Impossibility of distributed consensus with one faulty process
- Algebraic spans
- Uniform consensus is harder than consensus
- Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
- k-set agreement with limited accuracy failure detectors
- Generalized FLP impossibility result for t-resilient asynchronous computations