Fast lean erasure-coded atomic memory object
© Kishori M. Konwar, N. Prakash, Muriel Médard, and Nancy Lynch; licensed under Creative Commons License CC-BY 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). In this work, we propose FLECKS, an algorithm which implements atomic memory objects in a multi-writer mult...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137569 |
| _version_ | 1826211297270693888 |
|---|---|
| author | Konwar, KM Prakash, N Médard, M Lynch, N |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Konwar, KM Prakash, N Médard, M Lynch, N |
| author_sort | Konwar, KM |
| collection | MIT |
| description | © Kishori M. Konwar, N. Prakash, Muriel Médard, and Nancy Lynch; licensed under Creative Commons License CC-BY 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). 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. |
| first_indexed | 2024-09-23T15:04:00Z |
| format | Article |
| id | mit-1721.1/137569 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:04:00Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1375692023-02-09T20:13:22Z Fast lean erasure-coded atomic memory object Konwar, KM Prakash, N Médard, M Lynch, N Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science © Kishori M. Konwar, N. Prakash, Muriel Médard, and Nancy Lynch; licensed under Creative Commons License CC-BY 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). 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. 2021-11-05T18:35:45Z 2021-11-05T18:35:45Z 2019 2021-01-29T15:12:04Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137569 Konwar, KM, Prakash, N, Médard, M and Lynch, N. 2019. "Fast lean erasure-coded atomic memory object." Leibniz International Proceedings in Informatics, LIPIcs, 153. en 10.4230/LIPIcs.OPODIS.2019.12 Leibniz International Proceedings in Informatics, LIPIcs Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Konwar, KM Prakash, N Médard, M Lynch, N Fast lean erasure-coded atomic memory object |
| title | Fast lean erasure-coded atomic memory object |
| title_full | Fast lean erasure-coded atomic memory object |
| title_fullStr | Fast lean erasure-coded atomic memory object |
| title_full_unstemmed | Fast lean erasure-coded atomic memory object |
| title_short | Fast lean erasure-coded atomic memory object |
| title_sort | fast lean erasure coded atomic memory object |
| url | https://hdl.handle.net/1721.1/137569 |
| work_keys_str_mv | AT konwarkm fastleanerasurecodedatomicmemoryobject AT prakashn fastleanerasurecodedatomicmemoryobject AT medardm fastleanerasurecodedatomicmemoryobject AT lynchn fastleanerasurecodedatomicmemoryobject |