A topological treatment of early-deciding set-agreement

DOI10.1016/j.tcs.2008.10.002zbMath1157.68015OpenAlexW2150475919MaRDI QIDQ1004319

Bastian Pochon, Rachid Guerraoui, Maurice P. Herlihy

Publication date: 2 March 2009

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.10.002

zbMATH Keywords

topologylower boundtime complexityearly decisionoptimistic algorithm\(k\)-set-agreementlocal decision

Mathematics Subject Classification ID

Distributed systems (68M14) Network protocols (68M12) Distributed algorithms (68W15)

Related Items (3)

Of choices, failures and asynchrony: the many faces of set agreement ⋮ New combinatorial topology bounds for renaming: the lower bound ⋮ Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• The inherent price of indulgence
• Unifying synchronous and asynchronous message-passing models
• Round-by-round fault detectors (extended abstract)
• Tight bounds for k -set agreement
• The topological structure of asynchronous computability
• Early stopping in Byzantine agreement
• From a static impossibility to an adaptive lower bound
• Impossibility of distributed consensus with one faulty process
• Uniform consensus is harder than consensus
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Algebraic spans
• Distributed Computing

This page was built for publication: A topological treatment of early-deciding set-agreement