A coded shared atomic memory algorithm for message passing architectures

Viveck R. Cadambe; Nancy Lynch; Muriel Médard; Peter Musial

doi:10.1109/NCA.2014.44

A coded shared atomic memory algorithm for message passing architectures

Viveck R. Cadambe, Nancy Lynch, Muriel Médard, Peter Musial

Electrical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

15 Scopus citations

Abstract

This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains two main contributions: 1) We present an atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with 'N' servers that is resilient to 'f' server failures, we show that the communication cost of CAS is N/(N-2f). The storage cost of CAS is unbounded. 2) We present a variant of CAS known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer δ and has a bounded storage cost. We show that in every execution where the number of write operations that are concurrent with a read operation is no bigger than δ, the CASGC algorithm with parameter δ satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS.

Original language	English (US)
Title of host publication	Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	253-260
Number of pages	8
ISBN (Electronic)	9781479953936
DOIs	https://doi.org/10.1109/NCA.2014.44
State	Published - Oct 14 2014
Event	2014 13th IEEE International Symposium on Network Computing and Applications, NCA 2014 - Cambridge, United States Duration: Aug 21 2014 → Aug 23 2014

Publication series

Name	Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014

Other

Other	2014 13th IEEE International Symposium on Network Computing and Applications, NCA 2014
Country/Territory	United States
City	Cambridge
Period	8/21/14 → 8/23/14

All Science Journal Classification (ASJC) codes

Computer Science Applications
Computer Networks and Communications

Access to Document

10.1109/NCA.2014.44

Cite this

Cadambe, V. R., Lynch, N., Médard, M., & Musial, P. (2014). A coded shared atomic memory algorithm for message passing architectures. In Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014 (pp. 253-260). Article 6924235 (Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/NCA.2014.44

Cadambe, Viveck R. ; Lynch, Nancy ; Médard, Muriel et al. / A coded shared atomic memory algorithm for message passing architectures. Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014. Institute of Electrical and Electronics Engineers Inc., 2014. pp. 253-260 (Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014).

@inproceedings{f0b89689c8ec456a9dc453c1f7e2d87b,

title = "A coded shared atomic memory algorithm for message passing architectures",

abstract = "This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains two main contributions: 1) We present an atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with 'N' servers that is resilient to 'f' server failures, we show that the communication cost of CAS is N/(N-2f). The storage cost of CAS is unbounded. 2) We present a variant of CAS known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer δ and has a bounded storage cost. We show that in every execution where the number of write operations that are concurrent with a read operation is no bigger than δ, the CASGC algorithm with parameter δ satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS.",

author = "Cadambe, {Viveck R.} and Nancy Lynch and Muriel M{\'e}dard and Peter Musial",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 13th IEEE International Symposium on Network Computing and Applications, NCA 2014 ; Conference date: 21-08-2014 Through 23-08-2014",

year = "2014",

month = oct,

day = "14",

doi = "10.1109/NCA.2014.44",

language = "English (US)",

series = "Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "253--260",

booktitle = "Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014",

address = "United States",

}

Cadambe, VR, Lynch, N, Médard, M & Musial, P 2014, A coded shared atomic memory algorithm for message passing architectures. in Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014., 6924235, Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014, Institute of Electrical and Electronics Engineers Inc., pp. 253-260, 2014 13th IEEE International Symposium on Network Computing and Applications, NCA 2014, Cambridge, United States, 8/21/14. https://doi.org/10.1109/NCA.2014.44

A coded shared atomic memory algorithm for message passing architectures. / Cadambe, Viveck R.; Lynch, Nancy; Médard, Muriel et al.
Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014. Institute of Electrical and Electronics Engineers Inc., 2014. p. 253-260 6924235 (Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A coded shared atomic memory algorithm for message passing architectures

AU - Cadambe, Viveck R.

AU - Lynch, Nancy

AU - Médard, Muriel

AU - Musial, Peter

PY - 2014/10/14

Y1 - 2014/10/14

N2 - This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains two main contributions: 1) We present an atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with 'N' servers that is resilient to 'f' server failures, we show that the communication cost of CAS is N/(N-2f). The storage cost of CAS is unbounded. 2) We present a variant of CAS known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer δ and has a bounded storage cost. We show that in every execution where the number of write operations that are concurrent with a read operation is no bigger than δ, the CASGC algorithm with parameter δ satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS.

AB - This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains two main contributions: 1) We present an atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with 'N' servers that is resilient to 'f' server failures, we show that the communication cost of CAS is N/(N-2f). The storage cost of CAS is unbounded. 2) We present a variant of CAS known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer δ and has a bounded storage cost. We show that in every execution where the number of write operations that are concurrent with a read operation is no bigger than δ, the CASGC algorithm with parameter δ satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS.

UR - http://www.scopus.com/inward/record.url?scp=84911167192&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84911167192&partnerID=8YFLogxK

U2 - 10.1109/NCA.2014.44

DO - 10.1109/NCA.2014.44

M3 - Conference contribution

AN - SCOPUS:84911167192

T3 - Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014

SP - 253

EP - 260

BT - Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 13th IEEE International Symposium on Network Computing and Applications, NCA 2014

Y2 - 21 August 2014 through 23 August 2014

ER -

Cadambe VR, Lynch N, Médard M, Musial P. A coded shared atomic memory algorithm for message passing architectures. In Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014. Institute of Electrical and Electronics Engineers Inc. 2014. p. 253-260. 6924235. (Proceedings - 2014 IEEE 13th International Symposium on Network Computing and Applications, NCA 2014). doi: 10.1109/NCA.2014.44

A coded shared atomic memory algorithm for message passing architectures

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this