Parallel and Distributed Systems Group

Computer Science Department of Telecom SudParis

All You Need is DAG

Reading group: Minh Tung Nguyen presented "All You Need is DAG" (PODC'21) at Amphi 4 the 20/10/2023 at 10h00.


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.