Blockmania: from Block DAGs to Consensus
This addresses the need for scalable and efficient consensus protocols in distributed systems, particularly for dynamic membership and proof-of-stake applications, representing a novel method rather than an incremental improvement.
The authors tackled the problem of achieving Byzantine consensus efficiently by proposing Blockmania, a leaderless protocol using block DAGs, which achieves over 400K transactions per second on a wide area network with O(N^2) communication complexity, compared to O(N^4) for PBFT.
Blockmania is a byzantine consensus protocol. Nodes emit blocks forming a directed acyclic graph (block DAG) that is subsequently interpreted by each node separately to ensure consensus with safety, liveness and finality. The resulting system has communication complexity $O(N^2)$ even in the worse case, and very low constant factors --- as compared to $O(N^4)$ for PBFT; it is leaderless; and network operations do not depend on the composition of the quorum or node stake. This makes Blockmania very efficient (leading to over 400K transactions per second on a wide area network), and ideal for dynamic membership and flexible and non-interrupted proof-of-stake protocols. A X-Blockmania variant, has $O(N)$ communication cost but also higher latency $O(\log N)$.