Protocol Replicated Data Types
Consensus protocols built from replicated data types. Each replica accumulates knowledge until agreement is reached. Protocols are composed from small building blocks, and their safety is verified automatically.
Bismuth brings together several research strands of the Software Technology Group at TU Darmstadt: distributed reactive programming, replicated data types and protocols, and trust without a central authority. It contains the Scala implementations alongside the papers that formalize them, often with mechanizations in Lean. Bismuth is a continuation of REScala.
Developers work with ordinary data types and reactive signals. The platform takes care of replication and synchronization.
Each device works on its local state and synchronizes when it can. Coordination is only added where an application needs it.
Replicated data types, reactive dataflow, and access control compose. Programs built from them inherit their guarantees.
Most distributed applications today are built in one of two ways. Either developers write the communication themselves, and then also have to work out consistency, fault tolerance, and security for each application. Or they use cloud services, which handle these concerns but decide them for the application, and require all data to pass through the provider.
Bismuth explores a third option. Distribution is handled by programming abstractions that developers already know. Replicated data types are ordinary algebraic data types, and the merge of concurrent changes is derived from their structure. Reactive signals describe how values depend on each other, and updates propagate through these dependencies across devices. Access control and encryption are part of the replicated data itself, so no trusted server is needed.
Each device works on its local copy and stays usable without a network connection. Changes are synchronized when possible and all copies converge to the same state. Where an application needs stronger guarantees, for example to keep an invariant like a non-negative balance, coordination is added only for the affected operations. Consensus protocols themselves can be built from the same replicated data types.
The building blocks are designed to compose. Properties such as convergence or the safety of a protocol are proven for each building block, often mechanized in Lean, and then hold for programs built from them. The timeline below lists the individual projects and papers.
Consensus protocols built from replicated data types. Each replica accumulates knowledge until agreement is reached. Protocols are composed from small building blocks, and their safety is verified automatically.
Shows how the research strands fit together into one programming model. Replicated data types provide authentication and confidentiality, reactive function calls connect them into distributed dataflows, and automated reasoning finds where coordination is needed. Developers reason about local state, and the runtime makes sure all devices converge.
Access control for replicated data types without a central authority. Permissions follow the structure of the data and can be delegated and revoked at runtime. The permissions themselves are replicated as a tamper-evident hash DAG. Every replica checks them locally when exchanging updates, which keeps data confidential and intact even if some replicas are malicious.
Reactive programming for local-first applications. Developers state invariants, LoRe checks which concurrent interactions could violate them, and adds coordination only for those.
Local-first applications often synchronize through servers they do not trust. Because ARDTs are state-based, replicas can encrypt and sign their states end-to-end with a shared secret. Intermediaries can then store and forward data, but cannot read or modify it.
Developers replicate the data types they already use for their application logic, instead of picking from a fixed set of CRDTs. Every ARDT is a lattice, and merging is derived automatically from the structure of the type. Most other work in Bismuth builds on ARDTs, including LoRe, PRDTs, secure replication, and access control. documentation ↗
Automatic fault tolerance for distributed interactive applications, much like a garbage collector automates memory management. Combines thread-safe transactional change propagation, snapshots and recovery of reactive state, and replicated reactives based on CRDTs. Also applied to disruption-tolerant networks and Wi-Fi firmware.
REScala started as an extension of EScala (C#-style events in Scala). The goal was to bring functional reactive programming, inspired by projects such as FlapJax, into object-oriented code that students can use and understand. The API has stayed largely the same since 2014. In the PACE ERC project, REScala was extended to distributed software, which led to SID-UP, an update algorithm for distributed dataflow graphs without global coordination. rescala-lang.com ↗
Bismuth is developed at the Software Technology Group of TU Darmstadt. Anyone is welcome to join our matrix channel if you want to know more about our research or the Bismuth library.