PRDTs: Composable Design and Verification of Consensus Protocols using Replicated Data Types

Julian Haas, Ragnar Mogk, Annette Bieniusa, Mira Mezini · 2025

Read PRDTs: Composable Design and Verification of Consensus Protocols using Replicated Data Types by Julian Haas, Ragnar Mogk, Annette Bieniusa, Mira Mezini (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-05173.txt.

Introduction

Julian Haas, Mira Mezini and their co-authors propose protocol replicated data types, a way to build consensus protocols from composable parts in 2025. Consensus is core to distributed systems, but handcrafting a protocol for each use case is error-prone and forces full rewrites of known algorithms.

Their model uses replicated data types to gather knowledge step by step until agreement is reached, hiding network detail behind high-level logic. Known composition methods then let builders assemble complex protocols from verified blocks. A formal model and an automated proof procedure check safety of concrete designs. Working versions of known protocols performed without intrinsic slowdown.

Catalog record

CREATORJulian Haas, Ragnar Mogk, Annette Bieniusa, Mira Mezini
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-05173

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

PRDTs: Composable Design and Verification of Consensus Protocols using Replicated Data Types Julian Haas, Ragnar Mogk, Annette Bieniusa, Mira Mezini Abstract . Consensus protocols are fundamental in distributed systems as they enable services with strong consistency properties. However, designing protocols optimized for specific use-cases under certain system assumptions is typically an error-prone process requiring expert knowledge. Furthermore, while most recent optimized protocols are variations of well-known algorithms like Paxos or Raft, they often necessitate complete re-implementations, potentially introducing new bugs and complicating the application of existing verification results. This approach impedes application-specific consistency protocols that can easily be amended or swapped out, depending on the given application and deployment scenario. We propose Protocol Replicated Data Types (PRDTs), a novel programming model for implementing consensus protocols using replicated data types (RDTs). Inspired by the knowledge-based view of consensus, PRDTs employ RDTs to monotonically accumulate knowledge until agreement is reached. This approach allows for implementations focusing on high-level protocol logic that abstracts away network details and facilitates automated verification. Moreover, by applying existing algebraic composition techniques for RDTs in the PRDT context, we enable composable protocol building-blocks for implementing complex protocols. We present a formal model of our approach and implement a proof procedure that allows automated reasoning about the consensus safety of concrete PRDT implementations. Additionally, we demonstrate the applicability of our model in verified PRDT-based implementations of existing consensus protocols, and report empirical performance evaluation results. Our findings indicate that the PRDT approach offers enhanced flexibility and composability in protocol design, facilitates reasoning about correctness, and is suited for real-world adoption without intrinsic performance drawbacks. DOI: XXXXXXX.XXXXXXX Journal: JACM Volume: 37 4 111 8 1. Introduction In distributed systems, consensus is the foundation of strong consistency, creating order in a distributed environment and ensuring the correctness and reliability of crucial distributed services. However, establishing consensus often presents a performance bottleneck ( Brewer, 2012 ) , which has led to an active area of research developing custom protocols tailored to specific scenarios and application requirements ( Jha et al., 2019 ; Hunt et al., 2010 ; Kotla et al., 2010 ; Maiyya et al., 2019 ; Mao et al., 2008 ; Nawab et al., 2018 ; Ongaro and Ousterhout, 2014 ; Van Renesse and Altinbuken, 2015 ; Wei et al., 2017 ) . Developing correct custom (application-specific) consensus protocols is challenging. Existing programming and verification approaches for consensus force designers to reason about networks of concurrently operating processes that might fail or suffer from network partitions ( Wilcox et al., 2015 ; McMillan and Padon, 2018 ; McMillan and Padon, 2020 ; Hawblitzel et al., 2015 ) . Due to the inherent complexity of consensus, new designs are often variations of well-established and well-studied protocols ( Padon et al., 2017 ; Wang et al., 2019 ; Chandra et al., 2007 ; Howard et al., 2015 ; Lamport, 2005 ; Van Renesse and Altinbuken, 2015 ) . Despite being structurally similar to established designs, such variations are usually realized as distinct, monolithic implementations with subtle differences in system assumptions and use cases. This hinders the transfer of insights between protocols and increases the risk of introducing new bugs. Meanwhile, research on the “building blocks” that constitute a consensus protocol has only recently received attention ( Andersen and Sergey, 2021 ; Howard and Mortier, 2019 ; Howard and Mortier, 2020 ; Gupta et al., 2023 ; Jaber et al., 2021 ) . To improve performance and simplify reasoning, alternative knowledge-based approaches to the consensus problem have recently gained popularity. They follow the framing of agreement as a problem of knowledge by Halpern and Moses (1990) : To reach agreement (and thus consensus), processes have to establish eventual common knowledge , denoting facts that all processes will know eventually, and that remain valid thereafter. Through the exchange of facts, processes can try to lift local knowledge to eventual common knowledge in a monotonic process. The knowledge-based model improves performance and scalability of consensus protocols ( Jha et al., 2019 ; Chu et al., 2024 ) , while simplifying their formal safety verification ( Howard and Mortier, 2019 ; Nagasamudram et al., 2024 ; Lewchenko et al., 2025 ) . Motivated by these results, our work introduces protocol replicated data types (PRDTs) : a novel programming model that uses algebraic convergent replicated data types to enable developers to implement, compose, and customize consensus protocols for diverse systems and applications. PRDTs store the local knowledge of each process in a replicated data type, which ensures that the result of every local action becomes eventual common knowledge. Given this, the remaining responsibility of a PRDT implementation is to ensure that local actions can never create new knowledge that would invalidate existing decisions. Limiting the reasoning to local actions drastically simplifies reasoning about the correctness of a consensus implementation, as was recently demonstrated by Lewchenko et al. (2025) in a proof theory that was developed in parallel to our work on PRDTs. In this paper, we adapt their proof theory to our model and are able to show that PRDTs guarantee two of their proof obligations by design, further reducing the proof burden. PRDTs build upon algebraic replicated data types (ARDTs) ( Kuessner et al., 2023 ) and introduce specialized abstractions for systematically building safe consensus protocols on top of the convergent replicated state captured by the ARDT framework. ARDTs allow algebraic composition of existing replicated data types, and we demonstrate that this directly extends to PRDTs, fostering composable and parametric consensus protocols : developers can modularly assemble consensus protocols from provably correct components. This modular programming model encourages sharing and reuse of building blocks across protocols, reducing the risk of introducing subtle errors when adapting consensus mechanisms to new domains, while supporting compositional reasoning and verification . As a case study, we provide several executable implementations of distributed protocols from the Paxos family that we derive by composing simpler components, showcasing how PRDTs enable modular design and integrate with existing language features such as parametric algebraic data types, traits, and type classes ( Section 4 ). Finally, we conduct a performance evaluation 1 1 1 We plan to submit our performance evaluation and our PRDT implementations, verified with Stainless, for artifact evaluation. All of our implementations are FOSS under Apache-2.0 licence and will be made available with the non-anonymized version of this work. to empirically assess the practical feasibility of the PRDT model and the potential overhead they might introduce compared to existing message-based consensus protocol implementations ( Section 5 ). To this end, we implement a strongly consistent key-value store based on our PRDT implementation of Multi-Paxos and benchmark its performance in both local and geo-replicated settings. This evaluation provides a proof-of-principle that constructing practical systems using PRDT-based protocol implementations is feasible. Our prototype achieves parity with etcd ( etcd authors, 2024 ) and sometimes outperforms it in scenarios where the servers are colocated in the same data centre. Performance differences are visible in geo-replicated setups where etcd profits from optimizations in its key-value store layer (e.g., request pipelining), that we did not implement in our prototypical implementation. In summary, this paper makes the following contributions: • A dedicated programming model for knowledge-based compositional consensus protocols

Read the complete text