PnyxDB: a Lightweight Leaderless Democratic Byzantine Fault Tolerant Replicated Datastore

Byzantine-Fault-Tolerant (BFT) systems for closed consortia have recently attracted a growing attention notably in financial and supply-chain applications. Unfortunately, most existing solutions suffer from substantial scalability issues, and lack self-governance mechanisms. In this paper, we observe that many workloads present little concurrency, and propose PnyxDB, an eventually-consistent Byzantine Fault Tolerant replicated data-store that exhibits both high scalability and low latency. Our approach hinges on conditional endorsements that track conflicts between transactions. In addition to its high scalability, PnyxDB supports application-level voting, i.e. individual nodes are able to endorse or reject a transaction according to application-defined policies without compromising consistency. We provide a comparison against BFT-SMART and Tendermint, two competitors with different design aims, and show that our implementation speeds up commit latencies by a factor of 11, remaining below 5 seconds in a worldwide geodistributed deployment of 180 nodes.

I. Introduction

Byzantine Fault Tolerance (BFT) has attracted much attention over the last two decades [1],[2],[3],[4],[5],[6], and has now moved into the public spotlight following the rise of blockchain platforms. BFT systems typically rely on advanced replication protocols to ensure consistency between their replicas and withstand arbitrary failures and malicious behavior. Unfortunately, traditional BFT replication protocols struggle to scale beyond a few tens of replicas [7], while the proof-of-work technique used by many blockchain-based systems suffers from large computing and storage overheads.