A Topological Treatment of Early-Deciding Set-Agreement

DOI10.1007/11945529_3zbMATH Open1273.68066OpenAlexW1557833428MaRDI QIDQ3597941FDOQ3597941

Authors: Bastian Pochon, Rachid Guerraoui, Maurice Herlihy 

Publication date: 29 January 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11945529_3

Recommendations

• A topological treatment of early-deciding set-agreement
• The complexity of early deciding set agreement
• Tight bounds for \(k\)-set agreement
• The complexity of early deciding set agreement: how can topology help?
• From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement

zbMATH Keywords

lower boundtime complexityset-agreementearly global decision

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed systems (68M14)

Cited In (8)

• A non-topological proof for the impossibility of \(k\)-set agreement
• An overview of synchronous message-passing and topology
• Tight bounds for \(k\)-set agreement
• A topological treatment of early-deciding set-agreement
• The complexity of early deciding set agreement
• Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures
• From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement
• The complexity of early deciding set agreement: how can topology help?

This page was built for publication: A Topological Treatment of Early-Deciding Set-Agreement

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