More Web Proxy on the site http://driver.im/

article

Fast Paxos Made Easy: Theory and Implementation

Author:

Wenbing ZhaoAuthors Info & Claims

International Journal of Distributed Systems and Technologies, Volume 6, Issue 1

Pages 15 - 33

https://doi.org/10.4018/ijdst.2015010102

Published: 01 January 2015 Publication History

Abstract

Distributed consensus is one of the most important building blocks for distributed systems. Fast Paxos is one of the latest variants of the Paxos algorithm for distributed consensus. Fast Paxos allows an acceptor to cast a vote for a value of its choice unilaterally in a fast round, thereby eliminating a communication step for reaching consensus. As a tradeoff, the coordinator must build a quorum that is bigger than the simple majority used in Classic Paxos. This article presents the theory, implementation, and a comprehensive performance evaluation of the Fast Paxos algorithm. The theory is described in an easier-to-understand way compared with the original article by Lamport. In particular, an easy-to-implement value selection rule for the coordinator is derived. In the implementation of Fast Paxos for state-machine replication, a number of additional mechanisms are developed to cope with practical scenarios. Furthermore, the experiments reveal that Fast Paxos is most appropriate for use in a single-client configuration. The presence of two or more concurrent clients even in a local area network would incur frequent collisions, which would reduce the system throughput and increase the mean response time as experienced by clients. Due to frequent collisions, Fast Paxos actually performs worse than Classic Paxos in the presence of moderate to large number of concurrent clients.

References

[1]

Altinbuken, D., & Sirer, E. G. (2012). Commodifying replicated state machines with OpenReplica. Retrieved from http://openreplica.org/static/papers/OpenReplica.pdf

[2]

BoloskyW. J.BradshawD.HaagensR. B.KustersN. P.LiP. (2011, March). Paxos replicated state machines as the basis of a high-performance data store. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation (pp. 11-11). USENIX Association.

[3]

BurrowsM. (2006, November). The chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation (pp. 335-350). USENIX Association.

[4]

Camargos, L., Madeira, E. R., & Pedone, F. (2006). Optimal and practical wab-based consensus algorithms. In Proceedings of Euro-Par 2006 Parallel Processing (pp. 549-558). Springer Berlin Heidelberg.

[5]

Camargos, L., Schmidt, R., & Pedone, F. (2008, July). Multicoordinated agreement protocols for higher availabilty. In Proceedings of Network Computing and Applications, (pp. 76-84). IEEE. 10.1109/NCA.2008.28

Digital Library

[6]

ChandraT. D.GriesemerR.RedstoneJ. (2007, August). Paxos made live: An engineering perspective. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing (pp. 398-407). ACM. 10.1145/1281100.1281103

[7]

Charron-BostB.SchiperA. (2006, December). Improving fast paxos: Being optimistic with no overhead. In Proceedings of the 12th Pacific Rim International Symposium on Dependable Computing, (pp. 287-295). IEEE. 10.1109/PRDC.2006.39

Digital Library

[8]

Hunt, P., Konar, M., Junqueira, F. P., & Reed, B. (2010, June). ZooKeeper: wait-free coordination for internet-scale systems. In Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference (Vol. 8, pp. 11-11). USENIX.

[9]

Junqueira, F., Mao, Y., & Marzullo, K. (2007). Classic paxos vs. fast paxos: Caveat emptor. In Proceedings of USENIX Hot Topics in System Dependability (HotDep). USENIX.

[10]

Lamport, L. (2001). Paxos made simple. ACM Sigact News, 32(4), 18—25.

[11]

Lamport, L. (2006). Fast paxos. Distributed Computing, 19(2), 79—103.

Digital Library

[12]

Lamport, L., & Massa, M. (2004, June). Cheap paxos. In Proceedings of Dependable Systems and Networks, (pp. 307-314). IEEE. 10.1109/DSN.2004.1311900

[13]

Mao, Y., Junqueira, F. P., & Marzullo, K. (2008, December). Mencius: Building efficient replicated state machines for WANs. In Proceedings of OSDI (Vol. 8, pp. 369-384). OSDI.

[14]

Meling, H., & Jehl, L. (2013). Tutorial summary: Paxos explained from scratch. In Proceedings of OPODIS (LNCS), (vol. 8304, pp. 1-10). Springer.

[15]

Rao, J., Shekita, E. J., & Tata, S. (2011). Using Paxos to build a scalable, consistent, and highly available datastore. Proceedings of the VLDB Endowment, 4(4), 243—254.

Digital Library

[16]

Vieira, G., & Buzato, L. E. (2008). On the coordinator's rule for Fast Paxos. Information Processing Letters, 107(5), 183——187.

Digital Library

[17]

Vieira, G., & Buzato, L. E. (2013). The performance of Paxos and Fast Paxos. arXiv preprint arXiv:1308.1358.

[18]

ZhaoW. (2007, November). A lightweight fault tolerance framework for web services. In Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence (pp. 542-548). IEEE Computer Society. 10.1109/WI.2007.18

Digital Library

[19]

Zhao, W. (2010). Building highly dependable wireless web services. Journal of Electronic Commerce in Organizations, 8(4), 1—16.

Digital Library

[20]

Zhao, W. (2014). Building dependable distributed systems. John Wiley & Sons.

[21]

ZhaoW.Melliar-SmithP. M.MoserL. E. (2010, July). Fault tolerance middleware for cloud computing. In Proceedings of the 3rd IEEE International Conference on Cloud Computing, (pp. 67-74). IEEE.

Digital Library

[22]

Zhao, W., Zhang, H., & Chai, H. (2009). A lightweight fault tolerance framework for web services. Web Intelligence and Agent Systems, 7(3), 255—268.

Digital Library

Cited By

Shiozaki KNakamura J(2024)Selection Guidelines for Geographical SMR Protocols: A Communication Pattern-Based Latency Modeling ApproachStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-74498-3_25(344-359)Online publication date: 20-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-74498-3_25
Park SOusterhout JLorch JYu M(2019)Exploiting commutativity for practical fast replicationProceedings of the 16th USENIX Conference on Networked Systems Design and Implementation10.5555/3323234.3323240(47-64)Online publication date: 26-Feb-2019
https://dl.acm.org/doi/10.5555/3323234.3323240

Fast Paxos Made Easy: Theory and Implementation

Recommendations

Fast Flexible Paxos: Relaxing Quorum Intersection for Fast Paxos
ICDCN '21: Proceedings of the 22nd International Conference on Distributed Computing and Networking

Paxos, the de facto standard approach to solving distributed consensus, operates in two phases, each of which requires an intersecting quorum of nodes. Multi-Paxos reduces this to one phase by electing a leader but this leader is also a performance ...
Relaxed Paxos: quorum intersection revisited (again)
PaPoC '22: Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data

Distributed consensus, the ability to reach agreement in the face of failures, is a fundamental primitive for constructing reliable distributed systems. The Paxos algorithm is synonymous with consensus and widely utilized in production. Paxos uses two ...
Oblivious Paxos: Privacy-Preserving Consensus Over Secret-Shares
SoCC '23: Proceedings of the 2023 ACM Symposium on Cloud Computing

State-of-the-art consensus protocols like Paxos reveal the values being agreed upon to all nodes, but some deployment scenarios involving a subset of nodes outsourced to public cloud providers motivate hiding the value. In this work, we present the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Distributed Systems and Technologies

International Journal of Distributed Systems and Technologies Volume 6, Issue 1

January 2015

68 pages

ISSN:1947-3532

EISSN:1947-3540

Issue’s Table of Contents

Publisher

IGI Global

United States

Publication History

Published: 01 January 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shiozaki KNakamura J(2024)Selection Guidelines for Geographical SMR Protocols: A Communication Pattern-Based Latency Modeling ApproachStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-74498-3_25(344-359)Online publication date: 20-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-74498-3_25
Park SOusterhout JLorch JYu M(2019)Exploiting commutativity for practical fast replicationProceedings of the 16th USENIX Conference on Networked Systems Design and Implementation10.5555/3323234.3323240(47-64)Online publication date: 26-Feb-2019
https://dl.acm.org/doi/10.5555/3323234.3323240

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents