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

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

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)

• 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
• Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions

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)