Document Open Access Logo

The Case for Reconfiguration without Consensus: Comparing Algorithms for Atomic Storage

Authors Leander Jehl, Hein Meling

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.31.pdf
  • Filesize: 0.55 MB
  • 17 pages

Document Identifiers

Author Details

Leander Jehl
Hein Meling

Cite As Get BibTex

Leander Jehl and Hein Meling. The Case for Reconfiguration without Consensus: Comparing Algorithms for Atomic Storage. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.OPODIS.2016.31

Abstract

We compare different algorithms for reconfigurable atomic storage in the data-centric model. We present the first experimental evaluation of two recently proposed algorithms for reconfiguration without consensus and compare them to established algorithms for reconfiguration both with and without consensus.

Our evaluation reveals that the new algorithms offer a significant improvement in terms of latency and overhead for reconfiguration without consensus. Our evaluation also shows that reconfiguration without consensus, can obtain similar results to that of consensus-based reconfiguration, which relies on a stable leader. Moreover, the new algorithms also substantially reduces the overhead compared to consensus-based reconfiguration without a leader.

While our analysis confirms our intuition that batching reconfiguration requests serves to reduce the overhead of reconfigurations, our evaluation also shows that it is equally important to separate reconfigurations from read and write operations. Specifically, we found that using read and write operations to assist in completing concurrent reconfigurations is in fact detrimental to the reconfiguration performance.

Subject Classification

Keywords
  • atomic storage
  • reconfiguration
  • data-centric model

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Marcos Kawazoe Aguilera, Idit Keidar, Dahlia Malkhi, and Alexander Shraer. Dynamic atomic storage without consensus. J. ACM, 58(2), 2011. Google Scholar
  2. Masoud Saeida Ardekani and Douglas B. Terry. A self-configurable geo-replicated cloud storage system. In OSDI 2014. Google Scholar
  3. Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. J. ACM, 42(1):124-142, January 1995. URL: http://dx.doi.org/10.1145/200836.200869.
  4. Keren Censor-Hillel, Erez Petrank, and Shahar Timnat. Help! In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC'15, pages 241-250, New York, NY, USA, 2015. ACM. Google Scholar
  5. Gregory Chockler, Seth Gilbert, Vincent Gramoli, Peter M. Musial, and Alex A. Shvartsman. Reconfigurable distributed storage for dynamic networks. Journal of Parallel and Distributed Computing, 69(1), 2009. Google Scholar
  6. Gregory Chockler, Dahlia Malkhi, and Danny Dolev. A data-centric approach for scalable state machine replication. In André Schiper, AlexA. Shvartsman, Hakim Weatherspoon, and BenY. Zhao, editors, Future Directions in Distributed Computing, volume 2584 of Lecture Notes in Computer Science, pages 159-163. Springer Berlin Heidelberg, 2003. Google Scholar
  7. Partha Dutta, Rachid Guerraoui, Ron R Levy, and Marko Vukolic. Fast access to distributed atomic memory. SIAM Journal on Computing, Vol 39, N°8, December 2010, 2010. Google Scholar
  8. Jose M. Faleiro, Sriram Rajamani, Kaushik Rajan, G. Ramalingam, and Kapil Vaswani. Generalized lattice agreement. In PODC 2012, pages 125-134. ACM, 2012. Google Scholar
  9. Rui Fan and Nancy Lynch. Efficient replication of large data objects. In Faith Ellen Fich, editor, Distributed Computing: 17th International Conference, DISC 2003, Sorrento, Italy, October 1-3, 2003. Proceedings, pages 75-91. Springer, 2003. Google Scholar
  10. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374-382, April 1985. URL: http://dx.doi.org/10.1145/3149.214121.
  11. Eli Gafni and Dahlia Malkhi. Elastic configuration maintenance via a parsimonious speculating snapshot solution. In Yoram Moses, editor, Distributed Computing: 29th International Conference, DISC 2015. Proceedings, pages 140-153. Springer, 2015. Google Scholar
  12. S. Gilbert, N. Lynch, and A. Shvartsman. Rambo: a robust, reconfigurable atomic memory service for dynamic networks. Distr. Comp., 23(4), 2010. Google Scholar
  13. L. Jehl and H. Meling. Additional material. URL: http://www.ux.uis.no/~ljehl/pdf/thecase.pdf.
  14. Leander Jehl, Roman Vitenberg, and Hein Meling. Smartmerge: A new approach to reconfiguration for atomic storage. In Yoram Moses, editor, Distributed Computing: 29th International Conference, DISC 2015. Proceedings, pages 154-169. Springer, 2015. Google Scholar
  15. Leslie Lamport. On interprocess communication - part ii: Algorithms. Distributed Computing, 1(2):86-101, 1986. Google Scholar
  16. Leslie Lamport. Paxos made simple. ACM SIGACT News, 32(4):18-25, December 2001. Google Scholar
  17. Jacob R. Lorch, Atul Adya, William J. Bolosky, Ronnie Chaiken, John R. Douceur, and Jon Howell. The smart way to migrate replicated stateful services. In EuroSys, 2006. Google Scholar
  18. Charles Reiss, Alexey Tumanov, Gregory R. Ganger, Randy H. Katz, and Michael A. Kozuch. Heterogeneity and dynamicity of clouds at scale: Google trace analysis. In SOCC, 2012. Google Scholar
  19. Cheng Shao, Jennifer L. Welch, Evelyn Pierce, and Hyunyoung Lee. Multi-writer consistency conditions for the shared memory objects. In DISC 2003. Google Scholar
  20. Alexander Shraer, Jean-Philippe Martin, Dahlia Malkhi, and Idit Keidar. Data-centric reconfiguration with network-attached disks. In LADIS 2010. Google Scholar
  21. Daniel Steinberg and Stuart Cheshire. Zero Configuration Networking: The Definitive Guide. O'Reilly Media, Inc., 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact