Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures

DOI10.1007/s00224-008-9157-3zbMath1205.68093OpenAlexW2151618993MaRDI QIDQ987393

Michel Raynal, Philippe Raïpin Parvédy, Corentin Travers

Publication date: 13 August 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-008-9157-3

zbMATH Keywords

efficiencysynchronous systemcrash failure\(k\)-set agreementmessage-passing systemagreement problemearly decisionearly stoppingstrong terminationreceive omission failureround-based computationsend omission failure

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed systems (68M14)

Related Items

Of choices, failures and asynchrony: the many faces of set agreement

Cites Work

• Unnamed Item
• Tight bounds on the round complexity of distributed 1-solvable tasks
• 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.
• Structured derivations of consensus algorithms for failure detectors
• The Complexity of Early Deciding Set Agreement: How can Topology help?
• Tight bounds for k -set agreement
• The topological structure of asynchronous computability
• Simplifying fault-tolerance
• A combinatorial characterization of the distributed 1-solvable tasks
• Automatically increasing the fault-tolerance of distributed algorithms
• Early stopping in Byzantine agreement
• From a static impossibility to an adaptive lower bound
• A Topological Treatment of Early-Deciding Set-Agreement
• Strongly Terminating Early-Stopping k-Set Agreement in Synchronous Systems with General Omission Failures
• Distributed agreement in the presence of processor and communication faults
• Impossibility of distributed consensus with one faulty process
• Reaching Agreement in the Presence of Faults
• 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