Consensus algorithms with one-bit messages

DOI10.1007/BF01798957zbMATH Open0723.68012OpenAlexW2047188336MaRDI QIDQ757011FDOQ757011

Authors Amotz Bar-Noy, Danny Dolev

Publication date 1991

Published in Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

fault toleranceConsensus Problemone-bit messages

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Recommendations

• One-Step Consensus Solvability
• Consensus with ternary messages
• Modular construction of an efficient 1-bit Byzantine agreement protocol
• Message-optimal protocols for Byzantine Agreement
• A simple proof of a simple consensus algorithm
• ADAPTIVE AND DOUBLY-EXPEDITED ONE-STEP CONSENSUS IN BYZANTINE ASYNCHRONOUS SYSTEMS
• Low complexity Byzantine-resilient consensus
• Consensus in Byzantine asynchronous systems

Cites work

• A lower bound for the time to assure interactive consistency
• Coordinated Traversal: (t + 1)-Round Byzantine Agreement in Polynomial Time
• Fast Distributed Agreement
• Reaching Agreement in the Presence of Faults
• Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement

Cited in

(42)

• Scalable rational secret sharing
• Xheal, localized self-healing using expanders
• MIS on trees
• Fast and simple distributed consensus
• Conflict on a communication channel
• Coordinated consensus in dynamic networks
• Modular construction of an efficient 1-bit Byzantine agreement protocol
• Efficient agreement using fault diagnosis.
• scientific article; zbMATH DE number 1830912 (Why is no real title available?)
• Reconciling fault-tolerant distributed computing and systems-on-chip
• Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions
• Distributed deterministic edge coloring using bounded neighborhood independence
• Distributed graph coloring in a few rounds
• Total ordering algorithms for asynchronous Byzantine systems
• A flexible formal framework for masking/demasking faults
• Analyzing consistency properties for fun and profit
• Stability of a peer-to-peer communication system
• The impact of memory models on software reliability in multiprocessors
• Modular construction of a Byzantine agreement protocol with optimal message bit complexity
• A tight unconditional lower bound on distributed randomwalk computation
• Structuring unreliable radio networks
• Order optimal information spreading using algebraic gossip
• Byzantine-resistant total ordering algorithms.
• Fault-tolerant spanners
• Time-efficient randomized multiple-message broadcast in radio networks
• Byzantine agreement with homonyms
• Error-free multi-valued consensus with Byzantine failures
• On the microscopic view of time and messages
• Adaptively secure broadcast, revisited
• The round complexity of distributed sorting, extended abstract
• From bounded to unbounded concurrency objects and back
• Optimal-time adaptive strong renaming, with applications to counting
• Toward more localized local algorithms, removing assumptions concerning global knowledge
• Compact policy routing
• Locally checkable proofs
• A complexity separation between the cache-coherent and distributed shared memory models
• Faster information dissemination in dynamic networks via network coding
• The complexity of robust atomic storage
• Tight bounds on information dissemination in sparse mobile networks
• Cloture Votes:n/4-resilient Distributed Consensus int + 1 rounds
• Resilience of mutual exclusion algorithms to transient memory faults
• Minimum congestion mapping in a cloud

This page was built for publication: Consensus algorithms with one-bit messages

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