Optimal algorithms for synchronous Byzantine k-set agreement

DOI10.1016/J.TCS.2023.114098MaRDI QIDQ6093586zbMATH OpenOpenAlexFDO

Authors Carole Delporte-Gallet, Hugues Fauconnier, Michel Raynal, Mouna Safir

Publication date 7 September 2023

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

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

zbMATH Keywords

\(k\)-set agreementagreement problemByzantine processesdistributed algorithmdistributed computabilitymessage-passinground-based algorithmsynchronous system

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Recommendations

• Optimal algorithms for synchronous Byzantine \(k\)-set agreement
• Randomized k-set agreement in crash-prone and Byzantine asynchronous systems
• Narrowing Power vs. Efficiency in Synchronous Set Agreement
• Tight bounds for connectivity and set agreement in Byzantine synchronous systems
• A necessary condition for Byzantine \(k\)-set agreement

Cites work

• A lower bound for the time to assure interactive consistency
• A necessary condition for Byzantine \(k\)-set agreement
• Distributed Algorithms for Message-Passing Systems
• Distributed universality
• Fault-tolerant message-passing distributed systems. An algorithmic approach
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Generalized Universality
• Impossibility of distributed consensus with one faulty process
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Optimal algorithms for synchronous Byzantine \(k\)-set agreement
• Reaching Agreement in the Presence of Faults
• Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement
• The Byzantine Generals Problem
• The disagreement power of an adversary
• The topological structure of asynchronous computability
• Tight bounds for k-set agreement
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Which broadcast abstraction captures \(k\)-set agreement?

Cited in

(10)

• Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound
• Randomized k-set agreement in crash-prone and Byzantine asynchronous systems
• Strongly Terminating Early-Stopping k-Set Agreement in Synchronous Systems with General Omission Failures
• scientific article; zbMATH DE number 2006649 (Why is no real title available?)
• Narrowing Power vs. Efficiency in Synchronous Set Agreement
• Total ordering algorithms for asynchronous Byzantine systems
• Optimal algorithms for synchronous Byzantine \(k\)-set agreement
• Tight bounds for connectivity and set agreement in Byzantine synchronous systems
• Byzantine lattice agreement in synchronous message passing systems
• A necessary condition for Byzantine \(k\)-set agreement

This page was built for publication: Optimal algorithms for synchronous Byzantine \(k\)-set agreement

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