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

DOI10.1007/S00224-008-9157-3MaRDI QIDQ987393zbMATH OpenOpenAlexFDO

Authors Philippe Raïpin Parvédy, Michel Raynal, 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

\(k\)-set agreementagreement problemcrash failureearly decisionearly stoppingefficiencymessage-passing systemreceive omission failureround-based computationsend omission failurestrong terminationsynchronous system

Mathematics Subject Classification ID

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

Recommendations

• Strongly Terminating Early-Stopping k-Set Agreement in Synchronous Systems with General Omission Failures
• Tight bounds for connectivity and set agreement in Byzantine synchronous systems
• Failure detectors to solve asynchronous k-set agreement: a glimpse of recent results
• Agreement in synchronous networks with ubiquitous faults
• k-set agreement in communication networks with omission faults
• Tight bounds for \(k\)-set agreement with limited-scope failure detectors
• Tight bounds for k-set agreement with limited-scope failure detectors
• Tight bounds for \(k\)-set agreement with limited-scope failure detectors
• Randomized k-set agreement in crash-prone and Byzantine asynchronous systems

Cites work

• \(K\)-set agreement with limited accuracy failure detectors
• A combinatorial characterization of the distributed 1-solvable tasks
• A lower bound for the time to assure interactive consistency
• A simple bivalency proof that \(t\)-resilient consensus requires \(t+1\) rounds
• A simple proof of the uniform consensus synchronous lower bound.
• A Topological Treatment of Early-Deciding Set-Agreement
• Automatically increasing the fault-tolerance of distributed algorithms
• Distributed agreement in the presence of processor and communication faults
• Early stopping in Byzantine agreement
• From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement
• Generalized FLP impossibility result for t-resilient asynchronous computations
• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• Impossibility of distributed consensus with one faulty process
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Reaching Agreement in the Presence of Faults
• Simplifying fault-tolerance, providing the abstraction of crash failures
• Strongly Terminating Early-Stopping k-Set Agreement in Synchronous Systems with General Omission Failures
• Structured derivations of consensus algorithms for failure detectors
• The complexity of early deciding set agreement: how can topology help?
• The topological structure of asynchronous computability
• Tight bounds for k-set agreement
• Tight bounds on the round complexity of distributed 1-solvable tasks
• Uniform consensus is harder than consensus
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge

Cited in

(5)

• Of choices, failures and asynchrony: the many faces of set agreement
• A note on set agreement with omission failures
• k-set agreement in communication networks with omission faults
• Strongly Terminating Early-Stopping k-Set Agreement in Synchronous Systems with General Omission Failures
• Nearly-optimal consensus tolerating adaptive omissions: why a lot of randomness is needed?

This page was built for publication: Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures

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