Document Open Access Logo

Fast Lean Erasure-Coded Atomic Memory Object

Authors Kishori M. Konwar, N. Prakash, Muriel Médard, Nancy Lynch

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.12.pdf
  • Filesize: 1.39 MB
  • 17 pages

Document Identifiers

Author Details

Kishori M. Konwar
  • Department of EECS, MIT, Cambridge, USA
N. Prakash
  • Intel Inc, OR, USA
Muriel Médard
  • Department of EECS, MIT, Cambridge, USA
Nancy Lynch
  • Department of EECS, MIT, Cambridge, USA

Cite As Get BibTex

Kishori M. Konwar, N. Prakash, Muriel Médard, and Nancy Lynch. Fast Lean Erasure-Coded Atomic Memory Object. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.OPODIS.2019.12

Abstract

In this work, we propose FLECKS, an algorithm which implements atomic memory objects in a multi-writer multi-reader (MWMR) setting in asynchronous networks and server failures. FLECKS substantially reduces storage and communication costs over its replication-based counterparts by employing erasure-codes. FLECKS outperforms the previously proposed algorithms in terms of the metrics that to deliver good performance such as storage cost per object, communication cost a high fault-tolerance of clients and servers, guaranteed liveness of operation, and a given number of communication rounds per operation, etc. We provide proofs for liveness and atomicity properties of FLECKS and derive worst-case latency bounds for the operations. We implemented and deployed FLECKS in cloud-based clusters and demonstrate that FLECKS has substantially lower storage and bandwidth costs, and significantly lower latency of operations than the replication-based mechanisms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
Keywords
  • Atomicity
  • Distributed Storage System
  • Erasure-codes

Metrics

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

References

  1. Intel® Intelligent Storage Acceleration Library (Intel® ISA-L). https://software.intel.com/en-us/storage/ISA-L. [Online; accessed 23-August-2018].
  2. libstatgrab. https://www.i-scream.org/libstatgrab/. [Online; accessed 23-August-2018].
  3. ZeroMQ: Distributed Messaging. http://zeromq.org/. [Online; accessed 23-August-2018].
  4. H. Attiya, A. Bar-Noy, and D. Dolev. Sharing Memory Robustly in Message Passing Systems. Journal of the ACM, 42(1):124-142, 1996. Google Scholar
  5. Christian Cachin and Stefano Tessaro. Optimal Resilience for Erasure-Coded Byzantine Distributed Storage. In 2006 International Conference on Dependable Systems and Networks (DSN 2006), 25-28 June 2006, Philadelphia, Pennsylvania, USA, Proceedings, pages 115-124, Los Alamitos, CA, USA, 2006. IEEE Computer Society. URL: https://doi.org/10.1109/DSN.2006.56.
  6. Viveck R. Cadambe, Nancy A. Lynch, Muriel Médard, and Peter M. Musial. A coded shared atomic memory algorithm for message passing architectures. Distributed Computing, 30(1):49-73, 2017. Google Scholar
  7. Yu Lin Chen Chen, Shuai Mu, and Jinyang Li. Giza: Erasure coding objects across global data centers. In Proceedings of the 2017 USENIX Annual Technical Conference (USENIX ATC ’17), pages 539-551, 2017. Google Scholar
  8. Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo: Amazon’s Highly Available Key-value Store. In Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles, SOSP '07, pages 205-220, New York, NY, USA, 2007. ACM. URL: https://doi.org/10.1145/1294261.1294281.
  9. A. G. Dimakis, K. Ramchandran, Y. Wu, and C. Suh. A survey on network codes for distributed storage. Proceedings of the IEEE, 99(3):476-489, 2011. Google Scholar
  10. Partha Dutta, Rachid Guerraoui, and Ron R. Levy. Optimistic Erasure-Coded Distributed Storage. In DISC '08: Proceedings of the 22nd international symposium on Distributed Computing, pages 182-196, Berlin, Heidelberg, 2008. Springer-Verlag. URL: https://doi.org/10.1007/978-3-540-87779-0_13.
  11. G.R. Goodson, J.J. Wylie, G.R. Ganger, and M.K. Reiter. In Dependable Systems and Networks, 2004 International Conference on. URL: https://doi.org/10.1109/DSN.2004.1311884.
  12. James Hendricks, Gregory R Ganger, and Michael K Reiter. Low-overhead byzantine fault-tolerant storage. ACM SIGOPS Operating Systems Review, 41(6):73-86, 2007. Google Scholar
  13. W. C. Huffman and V. Pless. Fundamentals of error-correcting codes. Cambridge university press, 2003. Google Scholar
  14. K. M. Konwar, N. Prakash, E. Kantor, N. Lynch, M. Médard, and A. A. Schwarzmann. Storage-Optimized Data-Atomic Algorithms for Handling Erasures and Errors in Distributed Storage Systems. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 720-729, May 2016. Google Scholar
  15. Kishori M Konwar, N Prakash, Nancy Lynch, and Muriel Médard. RADON: Repairable atomic data object in networks. In The International Conference on Distributed Systems (OPODIS), 2016. Google Scholar
  16. Leslie Lamport. On Interprocess Communication, Part I: Basic Formalism. Distributed Computing, 1(2):77-85, 1986. Google Scholar
  17. Leslie Lamport. Fast Paxos. Distributed Computing, 19:79-103, October 2006. Google Scholar
  18. N Nicolaou, V Cadambe, N. Prakash, K.M. Konwar, M. Medard, and N Lynch. ARES: Adaptive, reconfigurable, erasure coded, atomic storage implementing a register in a dynamic distributed system. In International Conf. on Distributed Computing Systems (ICDCS), 2019. Google Scholar
  19. A. Spiegelman, Y. Cassuto, G. Chockler, and I. Keidar. Space Bounds for Reliable Storage: Fundamental Limits of Coding. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS2015), 2015. Google Scholar
  20. Heng Zhang, Mingkai Dong, and Haibo Chen. Efficient and Available In-memory KV-Store with Hybrid Erasure Coding and Replication. In 14th USENIX Conference on File and Storage Technologies (FAST 16), pages 167-180, 2016. 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