Tight bounds on the round complexity of distributed 1-solvable tasks

DOI10.1016/0304-3975(94)00157-EzbMATH Open0874.68144OpenAlexW1980697798MaRDI QIDQ673104FDOQ673104

Authors: Ofer Biran, Shlomo Moran, Shmuel Zaks 

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00157-e

Recommendations

• A combinatorial characterization of the distributed 1-solvable tasks
• Solvability in Asynchronous Environments II: Finite Interactive Tasks
• Renaming in an asynchronous environment
• Simultaneity is harder than agreement
• The extended BG-simulation and the characterization of t-resiliency

zbMATH Keywords

crash failure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Renaming in an asynchronous environment
• Initial failures in distributed computations
• Impossibility of distributed consensus with one faulty process
• On the minimal synchronism needed for distributed consensus
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Generalized FLP impossibility result for t-resilient asynchronous computations
• A combinatorial characterization of the distributed 1-solvable tasks
• Reaching approximate agreement in the presence of faults
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• The asynchronous computability theorem for t-resilient tasks
• Asynchronous approximate agreement

Cited In (4)

• Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures
• Hundreds of impossibility results for distributed computing
• A combinatorial characterization of the distributed 1-solvable tasks
• Algebraic topology and distributed computing

This page was built for publication: Tight bounds on the round complexity of distributed 1-solvable tasks

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