All You Need is DAG

2021/02/16 by Keidar, Idit, Kokoris-Kogias, Eleftherios, Naor, Oded +1 · 12 citations
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2102.08325

Abstract

We present DAG-Rider, the first asynchronous Byzantine Atomic Broadcast protocol that achieves optimal resilience, optimal amortized communication complexity, and optimal time complexity. DAG-Rider is post-quantum safe and ensures that all messages proposed by correct processes eventually get decided. We construct DAG-Rider in two layers: In the first layer, processes reliably broadcast their proposals and build a structured Directed Acyclic Graph (DAG) of the communication among them. In the second layer, processes locally observe their DAGs and totally order all proposals with no extra communication.

Cited by

• The Carnot Bound: Limits and Possibilities for Bandwidth-Efficient Consensus
• Declarative distributed algorithms as axiomatic theories in three-valued modal logic over semitopologies
• Sedna: Sharding transactions in multiple concurrent proposer blockchains
• MAD-DAG: Protecting Blockchain Consensus from MEV
• Lifefin: Escaping Mempool Explosions in DAG-based BFT
• BlueBottle: Fast and Robust Blockchains through Subsystem Specialization
• Resolving Conflicts with Grace: Dynamically Concurrent Universality
• MuPlon: Multi-Path Causal Optimization for Claim Verification through Controlling Confounding
• A Lightweight Approach for State Machine Replication
• Angelfish: Consensus with Optimal Throughput and Latency Across the Leader-DAG Spectrum
• Wait-free Replicated Data Types and Fair Reconciliation
• DAG it off: Latency Prefers No Common Coins

Related

• Bullshark: DAG BFT Protocols Made Practical
• DAG it off: Latency Prefers No Common Coins
• Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes
• Slim-ABC: An Optimized Atomic Broadcast Protocol
• Optimistic, Signature-Free Reliable Broadcast and Its Applications