All You Need is DAG

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

paper · pdf · doi:10.48550/arxiv.2102.08325

arxiv created 2021/06/04 · arxiv updated 2021/06/07

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
• From Permissioned to Proof-of-Stake Consensus
• DAGs for the Masses
• Optimistic, Signature-Free Reliable Broadcast and Its Applications
• Constitutional Consensus for Democratic Governance
• DAG-based Consensus with Asymmetric Trust [Extended Version]
• Transaction Fee Mechanism Design for Leaderless Blockchain Protocols
• Kudzu: Fast and Simple High-Throughput BFT
• Cassandra: Consensus with Partial Progress via Robust Partitionable View Synchronization
• Formal Verification of Blockchain Nonforking in DAG-Based BFT Consensus with Dynamic Stake
• Falcon: Advancing Asynchronous BFT Consensus for Lower Latency and Enhanced Throughput

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