On CRDTs in Byzantine Environments
| dc.contributor.author | Jacob, Florian | |
| dc.contributor.author | Bayreuther, Saskia | |
| dc.contributor.author | Hartenstein, Hannes | |
| dc.contributor.editor | Christian Wressnegger, Delphine Reinhardt | |
| dc.date.accessioned | 2023-01-24T11:17:53Z | |
| dc.date.available | 2023-01-24T11:17:53Z | |
| dc.date.issued | 2022 | |
| dc.description.abstract | Conflict-free Replicated Data Types (CRDTs) allow updates to be applied to different replicas independently and concurrently, without the need for a remote conflict resolution. Thus, they provide a building block for scalability and performance of fault-tolerant distributed systems. Currently, CRDTs are typically used in a crash fault setting for global scale, partition-tolerant, highly available databases or collaborative applications. In this paper, we explore the use of CRDTs in Byzantine environments. This exploration is inspired by the popular Matrix messaging system: as recently shown, the underlying Matrix Event Graph replicated data type represents a CRDT that can very well deal with Byzantine behavior. This “Byzantine Tolerance” is due to mechanisms inherent in CRDTs and in the hash-based directed acyclic graph (HashDAG) data structure used in Matrix. These mechanisms restrict Byzantine behavior. We, therefore, discuss Byzantine behavior in a context of CRDTs, and how the notion of Byzantine tolerance relates to equivocation. We show that a subclass of CRDTs is equivocation-tolerant, i.e., without equivocation detection, prevention or remediation, this subclass still fulfills the CRDT properties, which leads to Byzantine tolerance. We conjecture that an operation-based Byzantine-tolerant CRDT design supporting non-commutative operations needs to be based on a HashDAG data structure. We close the paper with thoughts on chances and limits of this data type. | en |
| dc.identifier.doi | 10.18420/sicherheit2022_07 | |
| dc.identifier.isbn | 978-3-88579-717-3 | |
| dc.identifier.pissn | 1617-5468 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/40149 | |
| dc.language.iso | en | |
| dc.publisher | Gesellschaft für Informatik, Bonn | |
| dc.relation.ispartof | GI SICHERHEIT 2022 | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Proceedings, Volume P-323 | |
| dc.subject | Dependable Distributed Protocols | |
| dc.subject | Conflict-Free Replicated Data Types | |
| dc.subject | Equivocation Tolerance | |
| dc.subject | Byzantine Fault Model | |
| dc.subject | Matrix Event Graph | |
| dc.title | On CRDTs in Byzantine Environments | en |
| gi.citation.endPage | 126 | |
| gi.citation.startPage | 113 | |
| gi.conference.date | 5.-8. April 2022 | |
| gi.conference.location | Karlsruhe | |
| gi.conference.sessiontitle | Session 2 |
Dateien
Originalbündel
1 - 1 von 1
Vorschaubild nicht verfügbar
- Name:
- B2-4.pdf
- Größe:
- 625.18 KB
- Format:
- Adobe Portable Document Format