Byzantine Eventual Consistency and Local-first Access Control

Slides from a talk given at the 12th Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC), Rotterdam, Netherlands, 31 March 2025.
https://martin.kleppmann.com/2025/03/31/papoc-keynote-byzantine.html
https://papoc-workshop.github.io/2025/program.html

Abstract:

CRDTs have long provided eventual consistency without a central server. But they have also long ignored the question: how do you know which peers are allowed to update the state? Performing access control without reintroducing a central server means we need a replicated data structure that stores the set of authorised users. This access control list is itself a CRDT, but it needs to be resilient against malicious manipulation. This talk will introduce how to think about Byzantine fault tolerance in eventually consistent systems, apply those principles to the problem of local-first access control, and show how these topics open exciting new research directions.

Transcript

33. PaPoC 2022
88. https://www.inkandswitch.com/keyhive/
91. References • Alex Good, John Mumm, and Brooklyn Zelenka. Keyhive lab notebook: Local-first access control. Ink & Switch, 2025. https://www.inkandswitch.com/keyhive/ • Martin Kleppmann. Making CRDTs Byzantine Fault Tolerant. PaPoC 2022. doi:10.1145/3517209.3524042 • Liangrun Da. Design and Verification of Byzantine Fault Tolerant CRDTs. Master’s Thesis, TU Munich, 2024. https://bit.ly/bft-crdt-isabelle • Martin Kleppmann and Heidi Howard. Byzantine Eventual Consistency and the Fundamental Limits of Peer-to-Peer Databases. Preprint, 2020. https://arxiv.org/abs/2012.00472 • Martin Kleppmann, Adam Wiggins, Peter van Hardenberg, and Mark McGranaghan. Local-first software: You own your data, in spite of the cloud. Onward! 2019. doi:10.1145/3359591.3359737 • Paper on ACL CRDT is work in progress, ask for draft 91