RIOT: Replicated Independently-Ordered Transactions

Abstract

Consensus protocols such as Raft and Paxos implement state machine replication through a single leader that enforces a totally ordered log. While this simplifies correctness, it introduces sequential bottlenecks that restrict scalability. We present RIOT, a generalized consensus protocol that eliminates centralized leadership and log replication in favor of decentralized coordination over a directed acyclic graph (DAG) of entries. RIOT guarantees that all servers maintain a logically identical DAG, preserving order where conflicts require it while allowing commutative operations to execute concurrently. RIOT is motivated by our work on distributed graph databases,which must guarantee reciprocal consistency for edges that span shards. Unlike specialized transaction protocols, RIOT makes no assumptions about concurrency control or transaction models. It provides a replicated state machine abstraction that integrates cleanly with transactional databases, treating DAG entries as transaction placeholders. Both single-phase and two-phase variants are supported, ensuring atomic agreement on entries and their ordering constraints. We integrate RIOT with Neo4j and evaluate it against Neo4j’s production Raft implementation. For common workloads, RIOT delivers up to 2.5× higher throughput and 2.3× lower tail latency while matching the strong consistency guarantees of log-based consensus. In doing so, RIOT demonstrates how consensus can be generalized to unlock scalability for transactional databases at scale.