Narrowing Power vs. Efficiency in Synchronous Set Agreement

DOI10.1007/978-3-540-77444-0_8MaRDI QIDQ5445741zbMATH OpenOpenAlexFDO

Authors Achour Mostefaoui, Michel Raynal, Corentin Travers

Publication date 6 March 2008

Published in Distributed Computing and Networking (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/inria-00139286/file/PI-1836.pdf

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Recommendations

• Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound
• The complexity of early deciding set agreement
• Tight bounds for k-set agreement
• Optimal algorithms for synchronous Byzantine \(k\)-set agreement
• A topological treatment of early-deciding set-agreement

Cites work

• \(K\)-set agreement with limited accuracy failure detectors
• A lower bound for the time to assure interactive consistency
• A simple bivalency proof that \(t\)-resilient consensus requires \(t+1\) rounds
• Algebraic spans
• Conditions on input vectors for consensus solvability in asynchronous distributed systems
• Early stopping in Byzantine agreement
• From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement
• Generalized FLP impossibility result for t-resilient asynchronous computations
• scientific article; zbMATH DE number 2013842 (Why is no real title available?)
• Impossibility of distributed consensus with one faulty process
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Narrowing Power vs. Efficiency in Synchronous Set Agreement
• Round-by-round fault detectors (extended abstract), unifying synchrony and asynchrony
• Synchronous condition-based consensus
• The combined power of conditions and failure detectors to solve asynchronous set agreement
• The topological structure of asynchronous computability
• Tight bounds for k-set agreement
• Tight bounds for k-set agreement with limited-scope failure detectors
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge

Cited in

(8)

• From adaptive renaming to set agreement
• Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound
• Partial synchrony based on set timeliness
• Of choices, failures and asynchrony: the many faces of set agreement
• Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers
• Narrowing Power vs. Efficiency in Synchronous Set Agreement
• Optimal algorithms for synchronous Byzantine \(k\)-set agreement
• Optimal algorithms for synchronous Byzantine \(k\)-set agreement

This page was built for publication: Narrowing Power vs. Efficiency in Synchronous Set Agreement

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