Consensus algorithms with one-bit messages

DOI10.1007/BF01798957zbMath0723.68012OpenAlexW2047188336MaRDI QIDQ757011

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)

Related Items

Coordinated consensus in dynamic networks ⋮ Error-free multi-valued consensus with byzantine failures ⋮ Distributed graph coloring in a few rounds ⋮ MIS on trees ⋮ Toward more localized local algorithms ⋮ The complexity of robust atomic storage ⋮ Resilience of mutual exclusion algorithms to transient memory faults ⋮ The impact of memory models on software reliability in multiprocessors ⋮ A complexity separation between the cache-coherent and distributed shared memory models ⋮ From bounded to unbounded concurrency objects and back ⋮ The space complexity of long-lived and one-shot timestamp implementations ⋮ Locally checkable proofs ⋮ Fault-tolerant spanners ⋮ Adaptively secure broadcast, revisited ⋮ Scalable rational secret sharing ⋮ Analyzing consistency properties for fun and profit ⋮ Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions ⋮ Optimal-time adaptive strong renaming, with applications to counting ⋮ The round complexity of distributed sorting ⋮ A tight unconditional lower bound on distributed randomwalk computation ⋮ Minimum congestion mapping in a cloud ⋮ Conflict on a communication channel ⋮ Stability of a peer-to-peer communication system ⋮ Tight bounds on information dissemination in sparse mobile networks ⋮ Time-efficient randomized multiple-message broadcast in radio networks ⋮ Faster information dissemination in dynamic networks via network coding ⋮ Modular construction of an efficient 1-bit Byzantine agreement protocol ⋮ Total ordering algorithms for asynchronous Byzantine systems ⋮ Reconciling fault-tolerant distributed computing and systems-on-chip ⋮ Order optimal information spreading using algebraic gossip ⋮ Fast and simple distributed consensus ⋮ Modular construction of a Byzantine agreement protocol with optimal message bit complexity ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ Structuring unreliable radio networks ⋮ Byzantine agreement with homonyms ⋮ Distributed deterministic edge coloring using bounded neighborhood independence ⋮ Compact policy routing ⋮ On the Microscopic View of Time and Messages ⋮ A flexible formal framework for masking/demasking faults ⋮ Xheal ⋮ Byzantine-resistant total ordering algorithms. ⋮ Efficient agreement using fault diagnosis.

Cites Work

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