Show simple item record

dc.contributor.advisorNancy Lynch
dc.contributor.authorCadambe, Viveck R.en_US
dc.contributor.authorLynch, Nancyen_US
dc.contributor.authorMedard, Murielen_US
dc.contributor.authorMusial, Peteren_US
dc.contributor.otherTheory of Computationen
dc.date.accessioned2013-07-17T18:45:04Z
dc.date.available2013-07-17T18:45:04Z
dc.date.issued2013-07-17
dc.identifier.urihttp://hdl.handle.net/1721.1/79606
dc.description.abstractThis paper considers the communication and storage costs of emulating atomic (linearizable) read/write shared memory in distributed message-passing systems. We analyze the costs of previously-proposed algorithms by Attiya, Bar-Noy, and Dolev (the ABD algorithm) and by Fan and Lynch (the LDR algorithm), and develop new coding-based algorithms that significantly reduce these costs. The paper contains three main contributions: (1) We present a new shared-memory algorithm that we call CAS, for Coded Atomic Storage. This algorithm uses erasure coding methods. (2) In a storage system with N servers that is resilient to f server failures, we show that the communication costs for the ABD and LDR algorithms, measured in terms of number of object values, are both at least f + 1, whereas the communication cost for CAS is N/(N-2f). (3) We also explicitly quantify the storage costs of the ABD, LDR, and CAS algorithms. The storage cost of the ABD algorithm, measured in terms of number of object values, is N; whereas the storage costs of the LDR and CAS algorithms are both unbounded. We present a modification of the CAS algorithm based on the idea of garbage collection. The modified version of CAS has a storage cost of (d + 1) N/(N-2f), where d in an upper bound on the number of operations that are concurrent with a read operation. Thus, if d is sufficiently small, the storage cost of CAS is lower than those of both the ABD and LDR algorithms.en_US
dc.format.extent24 p.en_US
dc.relation.ispartofseriesMIT-CSAIL-TR-2013-016
dc.titleCoded Emulation of Shared Atomic Memory for Message Passing Architecturesen_US
dc.date.updated2013-07-17T18:45:05Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record