Tight bounds for k -set agreement

DOI10.1145/355483.355489zbMath1320.68034OpenAlexW2056910803MaRDI QIDQ2946999

Maurice Erlihy, Mark R. Tuttle, Soma Chaudhuri, Nancy A. Lynch

Publication date: 19 September 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/355483.355489

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Network protocols (68M12)

Related Items (19)

Survey on Parameterized Verification with Threshold Automata and the Byzantine Model Checker ⋮ The topology of distributed adversaries ⋮ Optimal algorithms for synchronous Byzantine \(k\)-set agreement ⋮ Why Extension-Based Proofs Fail ⋮ Of choices, failures and asynchrony: the many faces of set agreement ⋮ Tight bounds for \(k\)-set agreement with limited-scope failure detectors ⋮ Hundreds of impossibility results for distributed computing ⋮ On the road to the weakest failure detector for \(k\)-set agreement in message-passing systems ⋮ Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures ⋮ Narrowing Power vs. Efficiency in Synchronous Set Agreement ⋮ A topological treatment of early-deciding set-agreement ⋮ The Complexity of Early Deciding Set Agreement: How can Topology help? ⋮ An Axiomatic Approach to Computing the Connectivity of Synchronous and Asynchronous Systems ⋮ A topological perspective on distributed network algorithms ⋮ Wait-free approximate agreement on graphs ⋮ Classifying rendezvous tasks of arbitrary dimension ⋮ Structured Derivation of Semi-Synchronous Algorithms ⋮ Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound ⋮ Back to the Coordinated Attack Problem

This page was built for publication: Tight bounds for k -set agreement