Fluidity: Location-Awareness in Replicated State Machines
Pages 192 - 201
Abstract
In planetary-scale replication systems, the overall response delay is greatly influenced by the geographical distances between client and server nodes. Current systems define the replica locations statically during startup time. However, the selected locations might be suboptimal for the clients, and the client request origin distribution may change over time, so a different replica placement may provide lower overall request latencies. In this work, we propose a location-aware replicated state machine that is able to adapt the geographic location of its replicas dynamically during runtime to locations geographically closer to client request origins. Our prototype is able to observe emerging optimization potentials and to reduce the overall request latency for the majority of clients by adapting its replica locations to the time-dependent optimum placement during real-world use case evaluations, whereby the absolute performance gain is dependent on the respective usage scenario.
References
[1]
Y. Amir, C. Danilov, J. Kirsch, J. Lane, D. Dolev, C. Nita-Rotaru, J. Olsen, and D. Zage. 2006. Scaling Byzantine Fault-Tolerant Replication to Wide Area Networks. In Int. Conf. on Dep. Sys. and Netw. (DSN). 105--114.
[2]
C. Berger, H. P. Reiser, J. Sousa, and A. Bessani. 2020. AWARE: Adaptive Wide-Area Replication for Fast and Resilient Byzantine Consensus. IEEE Trans. on Dep. and Sec. Comp. (2020), 1--1.
[3]
A. Bessani, J. Sousa, and E. E. P. Alchieri. 2014. State Machine Replication for the Masses with BFT-SMART. In 44th Int. Conf. on Dep. Sys. and Netw. (DSN). 355--362.
[4]
C. E. Bezerra, F. Pedone, and R. Van Renesse. 2014. Scalable State-Machine Replication. In 44th Int. Conf. on Dep. Sys. and Netw. (DSN). 331--342.
[5]
M. Castro and B. Liskov. 1999. Practical Byzantine Fault Tolerance. In 3rd Symp. on Oper. Sys. Des. and Impl. (OSDI). USENIX Assoc., USA, 173--186.
[6]
B.-G. Chun, P. Maniatis, S. Shenker, and J. Kubiatowicz. 2007. Attested Append-Only Memory: Making Adversaries Stick to Their Word. ACM SIGOPS Oper. Sys. Rev. 41, 6 (Oct. 2007), 189--204.
[7]
M. Eischer and T. Distler. 2018. Latency-Aware Leader Selection for Geo-Replicated Byzantine Fault-Tolerant Systems. In 48th Int. Conf. on Dep. Sys. and Netw. Workshops (DSN-W). 140--145.
[8]
M. Eischer and T. Distler. 2020. Resilient Cloud-based Replication with Low Latency. In 21st Int. Middleware Conf. (Middleware '20). ACM, New York, NY, USA, 14--28.
[9]
G. Habiger, F. J. Hauck, H. P. Reiser, and J. Köstler. 2020. Self-Optimising Application-agnostic Multithreading for Replicated State Machines. In Int. Symp. on Rel. Distr. Sys. (SRDS). 165--174.
[10]
J. O. Kephart and D. M. Chess. 2003. The Vision of Autonomic Computing. Comp. 36, 1 (Jan. 2003), 41--50.
[11]
S. Keshav, W. Golab, B. Wong, S. Rizvi, and S. Gorbunov. 2019. RCanopus: Making Canopus Resilient to Failures and Byzantine Faults. arXiv:1810.09300 [cs] (June 2019). arXiv:cs/1810.09300
[12]
L. Lamport. 1998. The Part-Time Parliament. ACM Trans. on Comp. Sys. 16, 2 (May 1998), 133--169.
[13]
L. Lamport, D. Malkhi, and L. Zhou. 2010. Reconfiguring a state machine. ACM SIGACT News 41, 1 (March 2010), 63--73.
[14]
L. H. Le, C. E. Bezerra, and F. Pedone. 2016. Dynamic Scalable State Machine Replication. In 46th Int. Conf. on Dep. Sys. and Netw. (DSN). 13--24.
[15]
Y. Mao, F. P. Junqueira, and K. Marzullo. 2008. Mencius: Building Efficient Replicated State Machines for WANs. In 8th Conf. on Oper. Sys. Des. and Impl. (OSDI). USENIX Assoc., USA, 369--384.
[16]
Y. Mao, F. P. Junqueira, and K. Marzullo. 2009. Towards Low Latency State Machine Replication for Uncivil Wide-Area Networks. In Worksh. on Hot Topics in Sys. Dep. (HotDep).
[17]
M. G. Merideth, F. Oprea, and M. K. Reiter. 2009. When and How to Change Quorums on Wide Area Networks. In 28th IEEE Int. Symp. on Rel. Distr. Sys. (SRDS). 12--21.
[18]
Z. Milosevic, M. Biely, and A. Schiper. 2013. Bounded Delay in Byzantine-Tolerant State Machine Replication. In 32nd IEEE Int. Symp. on Rel. Distr. Sys. 61--70.
[19]
S. Numakura, J. Nakamura, and R. Ohmura. 2019. Evaluation and Ranking of Replica Deployments in Geographic State Machine Replication. In 38th Int. Symp. on Rel. Distr. Sys. Workshops (SRDSW). 37--42.
[20]
R. Padilha and F. Pedone. 2013. Augustus: Scalable and Robust Storage for Cloud Applications. In 8th ACM Eur. Conf. on Comp. Sys. (EuroSys). ACM, New York, NY, USA, 99--112.
[21]
F. B. Schneider. 1990. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Comp. Surv. 22, 4 (Dec. 1990), 299--319.
[22]
J. Sousa and A. Bessani. 2015. Separating the WHEAT from the Chaff: An Empirical Design for Geo-Replicated State Machines. In 34th IEEE Symp. on Rel. Distr. Sys. (SRDS). 146--155.
[23]
G. S. Veronese, M. Correia, A. N. Bessani, and L. C. Lung. 2010. EBAWA: Efficient Byzantine Agreement for Wide-Area Networks. In 12th IEEE Int. Symp. on High Assurance Sys. Eng. 10--19.
[24]
G. S. Veronese, M. Correia, A. N. Bessani, L. C. Lung, and P. Verissimo. 2013. Efficient Byzantine Fault-Tolerance. IEEE Trans. on Comp. 62, 1 (Jan. 2013), 16--30.
[25]
W. Wei, H. T. Gao, F. Xu, and Q. Li. 2013. Fast Mencius: Mencius with Low Commit Latency. In IEEE INFOCOM. 881--889.
[26]
M. Zbierski. 2017. Towards Scalable Byzantine Fault-Tolerant Replication. In Photonics Applications in Astronomy, Communications, Industry, and High-Energy Physics Experiments, R. S. Romaniuk and M. Linczuk (Eds.). Wilga, Poland, 1044520.
Index Terms
- Fluidity: Location-Awareness in Replicated State Machines
Recommendations
Separating agreement from execution for byzantine fault tolerant services
SOSP '03We describe a new architecture for Byzantine fault tolerant state machine replication that separates agreement that orders requests from execution that processes requests. This separation yields two fundamental and practically significant advantages ...
Tolerating byzantine faults in transaction processing systems using commit barrier scheduling
SOSP '07: Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principlesThis paper describes the design, implementation, and evaluation of areplication scheme to handle Byzantine faults in transaction processing database systems. The scheme compares answers from queries and updates on multiple replicas which are unmodified, ...
Separating agreement from execution for byzantine fault tolerant services
SOSP '03: Proceedings of the nineteenth ACM symposium on Operating systems principlesWe describe a new architecture for Byzantine fault tolerant state machine replication that separates agreement that orders requests from execution that processes requests. This separation yields two fundamental and practically significant advantages ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2023
1932 pages
ISBN:9781450395175
DOI:10.1145/3555776
- Conference Chairs:
- Jiman Hong,
- Maart Lanperne,
- Program Chairs:
- Juw Won Park,
- Tomas Cerny,
- Publication Chair:
- Hossain Shahriar
Copyright © 2023 Owner/Author(s).
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 June 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
SAC '23
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,650 of 6,669 submissions, 25%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 183Total Downloads
- Downloads (Last 12 months)132
- Downloads (Last 6 weeks)14
Reflects downloads up to 30 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in