69. LOW LATENCY BYZANTINE STATE MACHINE REPLICATION FOR MUTUALLY SUSPICIOUS DOMAINS

Department: Computer Science & Engineering
Research Institute Affiliation: Center for Networked Systems (CNS)
Faculty Advisor(s): Keith Marzullo

Primary Student
Name: Yanhua Mao
Email: yamao@ucsd.edu
Phone: 858-534-9911
Grad Year: 2009

Abstract
Mutually Suspicious Domains (MSD) are communication domains in which trust is established inside, but not in between. Replicated state machine (RSM) approach is a fundamental approach to build highly available services. In MSD, this usually requires RSM protocols that tolerate Byzantine failures, i.e., arbitrary failures. However, existing Byzantine RSM protocols have relatively high latency in MSD, because (1) they are fixed leader protocols, therefore have higher latency at the non-leaders, and (2) they do not consider the special trust structure in MSD, therefore read operations have the same delay as write operations. Whereas existing protocols can use client or service side speculation to improve latency, this may not always be desirable as it increase the complexity of implementing upper level services. In this work, we propose Byzantine Mencius, a low-latency, rotating leader and non-speculative Byzantine RSM protocol derived from the original low latency and high throughput crash failure Mencius protocol. As a result, the new protocol has zero inter-domain delay for read operations. For write operations, Byzantine Mencius has the minimal two inter-domain communication step delay when there is no contention. When contention is present, Byzantine Mencius's latency can be up to three steps, which is also the theoretical minimal.

« Back to Posters or Search Results