PRDTs: Composable Knowledge-Based Consensus Protocols with Replicated Data Types
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913782866903040 |
|---|---|
| author | Haas, Julian Mogk, Ragnar Bieniusa, Annette Mezini, Mira |
| author_facet | Haas, Julian Mogk, Ragnar Bieniusa, Annette Mezini, Mira |
| contents | Consensus protocols are fundamental in distributed systems as they enable software with strong consistency properties. However, designing optimized protocols for specific use-cases under certain system assumptions is typically a laborious and error-prone process requiring expert knowledge. 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 stands in the way of 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 with minimal network environment assumptions. 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, demonstrate its application in PRDT-based implementations of existing protocols, and report empirical evaluation results. Our findings indicate that the PRDT approach offers enhanced flexibility and composability in protocol design, facilitates reasoning about correctness, and does not suffer from inherent performance limitations that would prevent its use in real-world applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_05173 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | PRDTs: Composable Knowledge-Based Consensus Protocols with Replicated Data Types Haas, Julian Mogk, Ragnar Bieniusa, Annette Mezini, Mira Programming Languages Distributed, Parallel, and Cluster Computing Consensus protocols are fundamental in distributed systems as they enable software with strong consistency properties. However, designing optimized protocols for specific use-cases under certain system assumptions is typically a laborious and error-prone process requiring expert knowledge. 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 stands in the way of 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 with minimal network environment assumptions. 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, demonstrate its application in PRDT-based implementations of existing protocols, and report empirical evaluation results. Our findings indicate that the PRDT approach offers enhanced flexibility and composability in protocol design, facilitates reasoning about correctness, and does not suffer from inherent performance limitations that would prevent its use in real-world applications. |
| title | PRDTs: Composable Knowledge-Based Consensus Protocols with Replicated Data Types |
| topic | Programming Languages Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2504.05173 |