Egalitarian Byzantine Fault Tolerance

Eischer M, Distler T (2021)

Publication Language: English

Publication Type: Conference contribution, Original article

Publication year: 2021

Event location: Perth AU


DOI: 10.1109/PRDC53464.2021.00019


Minimizing end-to-end latency in geo-replicated systems usually makes it necessary to compromise on resilience, resource efficiency, or throughput performance, because existing approaches either tolerate only crashes, require additional replicas, or rely on a global leader for consensus. In this paper, we eliminate the need for such tradeoffs by presenting ISOS, a leaderless replication protocol that tolerates up to f Byzantine faults with a minimum of 3 f + 1 replicas. To reduce latency in wide-area environments, ISOS relies on an efficient consensus algorithm that allows all participating replicas to propose new requests and thereby enables clients to avoid delays by submitting requests to their nearest replica. In addition, ISOS minimizes overhead by limiting message ordering to requests that conflict with each other (e.g., due to accessing the same state parts) and by already committing them after three communication steps if at least f + 1 replicas report each conflict. Our experimental evaluation with a geo-replicated key-value store shows that these properties allow ISOS to provide lower end-to-end latency than existing protocols, especially for use-case scenarios in which the clients of a system are distributed across multiple locations.

Authors with CRIS profile

Related research project(s)

How to cite


Eischer, M., & Distler, T. (2021). Egalitarian Byzantine Fault Tolerance. In Proceedings of the 2021 IEEE 26th Pacific Rim International Symposium on Dependable Computing (PRDC). Perth, AU.


Eischer, Michael, and Tobias Distler. "Egalitarian Byzantine Fault Tolerance." Proceedings of the 2021 IEEE 26th Pacific Rim International Symposium on Dependable Computing (PRDC), Perth 2021.

BibTeX: Download