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

DOI10.1016/0304-3975(94)00157-EMaRDI QIDQ673104zbMATHOpenAlexFDO

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

zbMATH Keywords

crash failure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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

Cites work

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

Cited in

(5)

• Algebraic topology and distributed computing
• Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures
• Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions
• A combinatorial characterization of the distributed 1-solvable tasks
• Hundreds of impossibility results for 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)