Rabia: Simplifying State-Machine Replication through Randomization

Haochen Pan; Jesse Tuglu; Neo Zhou; Tianshu Wang; Yicheng Shen; Xiong Zheng; Joseph Tassarotti; Lewis Tseng; Roberto Palmieri

doi:10.1145/3477132.3483582

Rabia: Simplifying State-Machine Replication through Randomization

Haochen Pan, Jesse Tuglu, Neo Zhou, Tianshu Wang, Yicheng Shen, Xiong Zheng, Joseph Tassarotti, Lewis Tseng, Roberto Palmieri

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We introduce Rabia, a simple and high performance framework for implementing state-machine replication (SMR) within a datacenter. The main innovation of Rabia is in using randomization to simplify the design. Rabia provides the following two features: (i) It does not need any fail-over protocol and supports trivial auxiliary protocols like log compaction, snapshotting, and reconfiguration, components that are often considered the most challenging when developing SMR systems; and (ii) It provides high performance, up to 1.5x higher throughput than the closest competitor (i.e., EPaxos) in a favorable setup (same availability zone with three replicas) and is comparable with a larger number of replicas or when deployed in multiple availability zones.

Original language	English (US)
Title of host publication	SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles
Publisher	Association for Computing Machinery, Inc
Pages	472-487
Number of pages	16
ISBN (Electronic)	9781450387095
DOIs	https://doi.org/10.1145/3477132.3483582
State	Published - Oct 26 2021
Event	28th ACM Symposium on Operating Systems Principles, SOSP 2021 - Virtual, Online, Germany Duration: Oct 26 2021 → Oct 29 2021

Publication series

Name	SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles

Conference

Conference	28th ACM Symposium on Operating Systems Principles, SOSP 2021
Country/Territory	Germany
City	Virtual, Online
Period	10/26/21 → 10/29/21

Keywords

Consensus
Formal Verification
SMR

ASJC Scopus subject areas

Computational Theory and Mathematics
Computer Science Applications
Software

Access to Document

10.1145/3477132.3483582

Cite this

Pan, H., Tuglu, J., Zhou, N., Wang, T., Shen, Y., Zheng, X., Tassarotti, J., Tseng, L., & Palmieri, R. (2021). Rabia: Simplifying State-Machine Replication through Randomization. In SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles (pp. 472-487). (SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles). Association for Computing Machinery, Inc. https://doi.org/10.1145/3477132.3483582

Rabia: Simplifying State-Machine Replication through Randomization. / Pan, Haochen; Tuglu, Jesse; Zhou, Neo et al.
SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles. Association for Computing Machinery, Inc, 2021. p. 472-487 (SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Pan, H, Tuglu, J, Zhou, N, Wang, T, Shen, Y, Zheng, X, Tassarotti, J, Tseng, L & Palmieri, R 2021, Rabia: Simplifying State-Machine Replication through Randomization. in SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles. SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles, Association for Computing Machinery, Inc, pp. 472-487, 28th ACM Symposium on Operating Systems Principles, SOSP 2021, Virtual, Online, Germany, 10/26/21. https://doi.org/10.1145/3477132.3483582

Pan H, Tuglu J, Zhou N, Wang T, Shen Y, Zheng X et al. Rabia: Simplifying State-Machine Replication through Randomization. In SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles. Association for Computing Machinery, Inc. 2021. p. 472-487. (SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles). doi: 10.1145/3477132.3483582

@inproceedings{1011104f36be4e0dabb18a7d0e46de4d,

title = "Rabia: Simplifying State-Machine Replication through Randomization",

abstract = "We introduce Rabia, a simple and high performance framework for implementing state-machine replication (SMR) within a datacenter. The main innovation of Rabia is in using randomization to simplify the design. Rabia provides the following two features: (i) It does not need any fail-over protocol and supports trivial auxiliary protocols like log compaction, snapshotting, and reconfiguration, components that are often considered the most challenging when developing SMR systems; and (ii) It provides high performance, up to 1.5x higher throughput than the closest competitor (i.e., EPaxos) in a favorable setup (same availability zone with three replicas) and is comparable with a larger number of replicas or when deployed in multiple availability zones.",

keywords = "Consensus, Formal Verification, SMR",

author = "Haochen Pan and Jesse Tuglu and Neo Zhou and Tianshu Wang and Yicheng Shen and Xiong Zheng and Joseph Tassarotti and Lewis Tseng and Roberto Palmieri",

note = "Funding Information: The authors thank our shepherd Manos Kapritsos and all anonymous reviewers and artifact reviewers for their important comments. This material is based upon work supported by the National Science Foundation under Grant No. CNS-1816487 and CNS-2045976. Early evaluation and artifact evaluation of this work were obtained using the CloudLab testbed [24] supported by the National Science Foundation. The authors would also like to thank Matthew Abbene and Andrew Chapman{\textquoteright}s help on Redis integration, and Rachel Trickett{\textquoteright}s help on artifact evaluation. Publisher Copyright: {\textcopyright} 2021 ACM.; 28th ACM Symposium on Operating Systems Principles, SOSP 2021 ; Conference date: 26-10-2021 Through 29-10-2021",

year = "2021",

month = oct,

day = "26",

doi = "10.1145/3477132.3483582",

language = "English (US)",

series = "SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles",

publisher = "Association for Computing Machinery, Inc",

pages = "472--487",

booktitle = "SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles",

}

TY - GEN

T1 - Rabia

T2 - 28th ACM Symposium on Operating Systems Principles, SOSP 2021

AU - Pan, Haochen

AU - Tuglu, Jesse

AU - Zhou, Neo

AU - Wang, Tianshu

AU - Shen, Yicheng

AU - Zheng, Xiong

AU - Tassarotti, Joseph

AU - Tseng, Lewis

AU - Palmieri, Roberto

N1 - Funding Information: The authors thank our shepherd Manos Kapritsos and all anonymous reviewers and artifact reviewers for their important comments. This material is based upon work supported by the National Science Foundation under Grant No. CNS-1816487 and CNS-2045976. Early evaluation and artifact evaluation of this work were obtained using the CloudLab testbed [24] supported by the National Science Foundation. The authors would also like to thank Matthew Abbene and Andrew Chapman’s help on Redis integration, and Rachel Trickett’s help on artifact evaluation. Publisher Copyright: © 2021 ACM.

PY - 2021/10/26

Y1 - 2021/10/26

N2 - We introduce Rabia, a simple and high performance framework for implementing state-machine replication (SMR) within a datacenter. The main innovation of Rabia is in using randomization to simplify the design. Rabia provides the following two features: (i) It does not need any fail-over protocol and supports trivial auxiliary protocols like log compaction, snapshotting, and reconfiguration, components that are often considered the most challenging when developing SMR systems; and (ii) It provides high performance, up to 1.5x higher throughput than the closest competitor (i.e., EPaxos) in a favorable setup (same availability zone with three replicas) and is comparable with a larger number of replicas or when deployed in multiple availability zones.

AB - We introduce Rabia, a simple and high performance framework for implementing state-machine replication (SMR) within a datacenter. The main innovation of Rabia is in using randomization to simplify the design. Rabia provides the following two features: (i) It does not need any fail-over protocol and supports trivial auxiliary protocols like log compaction, snapshotting, and reconfiguration, components that are often considered the most challenging when developing SMR systems; and (ii) It provides high performance, up to 1.5x higher throughput than the closest competitor (i.e., EPaxos) in a favorable setup (same availability zone with three replicas) and is comparable with a larger number of replicas or when deployed in multiple availability zones.

KW - Consensus

KW - Formal Verification

KW - SMR

UR - http://www.scopus.com/inward/record.url?scp=85119098831&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85119098831&partnerID=8YFLogxK

U2 - 10.1145/3477132.3483582

DO - 10.1145/3477132.3483582

M3 - Conference contribution

AN - SCOPUS:85119098831

T3 - SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles

SP - 472

EP - 487

BT - SOSP 2021 - Proceedings of the 28th ACM Symposium on Operating Systems Principles

PB - Association for Computing Machinery, Inc

Y2 - 26 October 2021 through 29 October 2021

ER -

Rabia: Simplifying State-Machine Replication through Randomization

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this