DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2019.12

Fast Lean Erasure-Coded Atomic Memory Object

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

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{konwar_et_al:LIPIcs.OPODIS.2019.12,
  author =	{Konwar, Kishori M. and Prakash, N. and M\'{e}dard, Muriel and Lynch, Nancy},
  title =	{{Fast Lean Erasure-Coded Atomic Memory Object}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.12},
  URN =		{urn:nbn:de:0030-drops-117988},
  doi =		{10.4230/LIPIcs.OPODIS.2019.12},
  annote =	{Keywords: Atomicity, Distributed Storage System, Erasure-codes}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2016.28

RADON: Repairable Atomic Data Object in Networks

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

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract

Erasure codes offer an efficient way to decrease storage and communication costs while implementing atomic memory service in asynchronous distributed storage systems. In this paper, we provide erasure-code-based algorithms having the additional ability to perform background repair of crashed nodes. A repair operation of a node in the crashed state is triggered externally, and is carried out by the concerned node via message exchanges with other active nodes in the system. Upon completion of repair, the node re-enters active state, and resumes participation in ongoing and future read, write, and repair operations. To guarantee liveness and atomicity simultaneously, existing works assume either the presence of nodes with stable storage, or presence of nodes that never crash during the execution. We demand neither of these; instead we consider a natural, yet practical network stability condition N1 that only restricts the number of nodes in the crashed/repair state during broadcast of any message. We present an erasure-code based algorithm RADON_{C} that is always live, and guarantees atomicity as long as condition N1 holds. In situations when the number of concurrent writes is limited, RADON_{C} has significantly improved storage and communication cost over a replication-based algorithm RADON_{R}, which also works under N1. We further show how a slightly stronger network stability condition N2 can be used to construct algorithms that never violate atomicity. The guarantee of atomicity comes at the expense of having an additional phase during the read and write operations.

Cite as

Kishori M. Konwar, N. Prakash, Nancy A. Lynch, and Muriel Médard. RADON: Repairable Atomic Data Object in Networks. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{konwar_et_al:LIPIcs.OPODIS.2016.28,
  author =	{Konwar, Kishori M. and Prakash, N. and Lynch, Nancy A. and M\'{e}dard, Muriel},
  title =	{{RADON: Repairable Atomic Data Object in Networks}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.28},
  URN =		{urn:nbn:de:0030-drops-70970},
  doi =		{10.4230/LIPIcs.OPODIS.2016.28},
  annote =	{Keywords: Atomicity, repair, fault-tolerance, storage cost, erasure codes}
}

Search Results

Documents authored by Médard, Muriel

Fast Lean Erasure-Coded Atomic Memory Object

Abstract

Cite as

RADON: Repairable Atomic Data Object in Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message