A coded shared atomic memory algorithm for message passing architectures

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 three 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 \(\frac{N}{N-2f}\). The storage cost of CAS is unbounded. (2) We present a modification of the CAS algorithm known as CAS with garbage collection (CASGC). The CASGC algorithm is parameterized by an integer \(\delta \) and has a bounded storage cost. We show that the CASGC algorithm satisfies atomicity. In every execution of CASGC where the number of server failures is no bigger than f, we show that every write operation invoked at a non-failing client terminates. We also show that in an execution of CASGC with parameter \(\delta \) where the number of server failures is no bigger than f,  a read operation terminates provided that the number of write operations that are concurrent with the read is no bigger than \(\delta \). We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS. (3) We describe an algorithm known as the Communication Cost Optimal Atomic Storage (CCOAS) algorithm that achieves a smaller communication cost than CAS and CASGC. In particular, CCOAS incurs read and write communication costs of \(\frac{N}{N-f}\) measured in terms of number of object values. We also discuss drawbacks of CCOAS as compared with CAS and CASGC.

1. The algorithm of Attiya et al. [8] allows only a single node to act as a writer. Also, it did not distinguish between client and server nodes as we do in our paper.

2. Informally, an operation \(\pi \) is ongoing at a point P in an execution \(\beta \) if the point P is after the invocation of the operation \(\pi \), and there are steps taken on behalf of the operation \(\pi \) after point P in \(\beta \).

3. As we shall see later, the server gossip is not essential to correctness of CAS. It is however useful as a theoretical tool to prove correctness of CASGC.

4. The idea of registering a client’s identity was introduced originally in [29] and plays an important role in our CCOAS algorithm as well.

5. Strictly speaking, we need \(\lceil \log _{2}|\mathcal {V}|\rceil \) bits since the number of bits has to be an integer. We ignore this rounding error.

6. We assume that \(N > 2f,\) since correctness cannot be guaranteed if \(N \le 2f\) [26].

7. The ‘\(\mathrm {null}\)’ entry indicates that no coded element is stored; the storage cost associated storing a \(\mathrm {null}\) coded element is negligible.

8. It is worth noting that \(Q_{fw}\) and \(Q_{pw}\) need not be the same quorum.

9. An operation is said to have failed if the client performing the operation fails after its invocation but before its termination.

10. It is instructive to note that CAS\('\) does not satisfy the same liveness properties as CAS since servers may never respond to finalize messages from a reader in CAS\('\), even in a fair execution.

11. If the number of writes that are concurrent with a read operation is larger than \(\delta \), then the read simply may not terminate.

12. Note that in this second scenario, the server does not respond with a coded element in CAS, where the server only sends an acknowledgement. In contrast to the proof here, the liveness proof of CAS involved showing that at least k servers satisfy the condition imposed by the first scenario.

13. Literature in coding theory literature often studies the rate \(\frac{N}{k}\) of a code, which is the reciprocal of the redundancy factor, i.e., the rate of an (N, k) code is \(\frac{k}{N}.\) In this paper, we use the redundancy factor in our discussions since it enables a somewhat more intuitive connection with the costs of our algorithms in Theorems 13, 14, 4, 7.

14. This is unlike ABD where the servers store only the latest version of the data object received.

Authors and Affiliations

1. Department of Electrical Engineering, Pennsylvania State University, University Park, PA, USA

   Viveck R. Cadambe

2. Computer Science and Artificial Intelligence Laboratory (CSAIL), Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology (MIT), Cambridge, MA, USA

   Nancy Lynch

3. Research Laboratory of Electronics (RLE), Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology (MIT), Cambridge, MA, USA

   Muriel Mèdard

4. Advanced Storage Division, EMC Corporation, Cambridge, MA, USA

   Peter Musial

Corresponding author

Correspondence to Viveck R. Cadambe.

This work was supported in part by AFOSR Contract Numbers FA9550-13-1-0023, FA9550-14-1-0043, NSF Award Numbers CCF-1217506, CCF-0939370, CCF-1553248, and by BAE Systems National Security Solutions, Inc., award 739532-SLIN 0004.

The results of this work have partially appeared in a conference paper [11]. The paper [11] does not contain proofs of atomicity, liveness, and the costs incurred by the published algorithms. [11] does not include the CCOAS algorithm of Sect. 6 as well.

Appendix A: Discussion on erasure codes

For an (N, k) code, the ratio \(\frac{N}{k}\)—also known as the redundancy factor of the code—represents the storage cost overhead in the classical erasure coding model. Much literature in coding theory involves the design of (N, k) codes for which the redundancy factor^{Footnote 13} can be made as small as possible. In the classical erasure coding model, the extent to which the redundancy factor can be reduced depends on f—the maximum number of server failures that are to be tolerated. In particular, an (N, k) MDS code, when employed to store the value of the data object, tolerates \(N-k\) server node failures; this is because the definition of an MDS code implies that the data can be recovered from any k surviving nodes. Thus, for an N-server system that uses an MDS code, we must have \(k \le N-f\), meaning that the redundancy factor is at least \(\frac{N}{N-f}\). It is well known [32] that, given N and f, the parameter k cannot be made larger than \(N-f\) so that the redundancy factor is lower bounded by \(\frac{N}{N-f}\) for any code even if it is not an MDS code; In fact, an MDS code can equivalently be defined as one which attains this lower bound on the redundancy factor. In coding theory, this lower bound is known as the Singleton bound [32]. Given parameters N, k,  the question of whether an (N, k) MDS code exists depends on the alphabet of code \(\mathcal {W}\). We next discuss some of the relevant assumptions that we (implicitly) make in this paper to enable the use of an (N, k) MDS code in our algorithms.

Write protocol of the ABD algorithm

Full size image

1.1 Assumption on \(|\mathcal {V}|\) due to erasure coding

Recall that, in our model, each value v of a data object belongs to a finite set \(\mathcal {V}\). In our system, for the use of coding, we assume that \(\mathcal {V}=\mathcal {W}^{k}\) for some finite set \(\mathcal {W}\) and that \(\varPhi :\mathcal {W}^{k} \rightarrow \mathcal {W}^{N}\) is an MDS code. Here we refine these assumptions using classical results from erasure coding theory. In particular, the following result is useful.

Theorem 12

Consider a finite set \(\mathcal {W}\) such that \(|\mathcal {W}| \ge {N}.\) Then, for any integer \(k < N\), there exists an (N, k) MDS code \(\varPhi :\mathcal {W}^{k} \rightarrow \mathcal {W}^{N}\).

One proof for the above in coding theory literature is constructive. Specifically, it is well known that when \(|\mathcal {W}| \ge {N}\), then \(\varPhi \) can be constructed using the Reed-Solomon code construction [24, 31, 32]. The above theorem implies that, to employ a Reed-Solomon code over our system, we shall need the following two assumptions:

• k divides \(\log _2|\mathcal {V}|,\) and

• \(\log _{2}|\mathcal {V}|/k ~\ge ~ \log _{2}N\).

Thus all our results are applicable under the above assumptions.

Read protocol of the ABD algorithm

Full size image

Server protocol of the ABD algorithm

Full size image

Write protocol of the LDR algorithm

Full size image

Read protocol of the LDR algorithm

Full size image

In fact, the first assumption above can be replaced by a different assumption with only a negligible effect on the communication and storage costs. Specifically, if \(\log _2|\mathcal {V}|\) were not a multiple of k then, one could pad the value with \(\left( \lceil \frac{\log _2{|\mathcal {V}}|}{k}\rceil k - \log _2|\mathcal {V}|\right) \) “dummy” bits, all set to 0, to ensure that the (padded) object has a size that is multiple of k; note that this padding is an overhead. The size of the padded object would be \(\lceil \frac{\log _2{|\mathcal {V}|}}{k}\rceil k\) bits and the size of each coded element would be \(\lceil \frac{\log _2{|\mathcal {V}|}}{k}\rceil \) bits. If we assume that \(\log _{2}|\mathcal {V}| \gg k\) then, \(\lceil \frac{\log _2{|\mathcal {V}|}}{k}\rceil \approx \frac{\log _{2}|\mathcal {V}|}{k}\) meaning that the padding overhead can be neglected. Consequently, the first assumption can be replaced by the assumption that \(\log _{2}|\mathcal {V}| \gg k\) with only a negligible effect on the communication and storage costs.

Appendix B: Descriptions of the ABD and LDR algorithms

As baselines for our work we use the MWMR versions of the ABD and LDR algorithms [8, 16]. Here, we describe the ABD and LDR algorithms, and evaluate their communication and storage costs. We present the ABD algorithm in Figs. 8, 9 and 10. We present the LDR algorithm in Figs. 11, 12 and 13. The costs of these algorithms are stated in Theorems 13 and 14.

Theorem 13

The write and read communication costs of ABD are respectively equal to \(N \log |\mathcal {V}|\) and \({2N} \log |\mathcal {V}|\) bits. The storage cost is equal to N \(\log _2|\mathcal {V}|\) bits.

The LDR algorithm divides its servers into directory servers that store metadata, and replica servers that store object values. The write protocol of LDR involves the sending of object values to \(2f+1\) replica servers. The read protocol is less taxing since in the worst-case, it involves retrieving the data object values from \(f+1\) replica servers. We state the communication costs of LDR next (for formal proof, see Appendix 1.)

Theorem 14

In LDR, the write communication cost is \((2f+1)\) \(\log _2|\mathcal {V}|\) bits, and the read communication cost is \((f+1)\) \(\log _2|\mathcal {V}|\) bits.

In the LDR algorithm, each replica server stores every version of the data object it receives.^{Footnote 14} Therefore, the (worst-case) storage cost of the LDR algorithm is unbounded.

Replica and directory server protocols of the LDR algorithm

Full size image

Proof of Theorem 13

We first present arguments that upper bound the communication and storage cost for every execution of the ABD algorithm. The ABD algorithm presented here is fitted to our model. Specifically in [8, 25] there is no clear cut separation between clients and servers. However, this separation does not change the costs of the algorithm. Then we present worst-case executions that incur the costs as stated in the theorem.

Upper bounds First consider the write protocol. It has two phases, get and put. The get phase of a write involves transfer of a tag, but not of actual data, and therefore has negligible communication cost. In the put phase of a write, the client sends a value from the set \(\mathcal {T} \times \mathcal {V}\) to every server node; the total communication cost of this phase is at most \(N \log _2|\mathcal {V}|\) bits. Therefore the total write communication cost is at most \(N \log _{2}|\mathcal {V}|\) bits. In the get phase of the read protocol, the message from the client to the servers contains only metadata, and therefore has negligible communication cost. However, in this phase, each of the N servers could respond to the client with a message from \(\mathcal {T} \times \mathcal {V}\); therefore the total communication cost of the messages involved in the get phase is upper bounded by \(N \log _{2}|\mathcal {V}|\) bits. In the put phase of the read protocol, the read sends an element of \(\mathcal {T} \times \mathcal {V}\) to N servers. Therefore, this phase incurs a communication cost of at most \( {N} \log _{2}|\mathcal {V}|\) bits. The total communication cost of a read is therefore upper bounded by \({2N }\log _{2}|\mathcal {V}|\) bits.

The storage cost of ABD is no bigger than \(N\log _{2}|\mathcal {V}|\) bits because each server stores at most one value - the latest value it receives.

Worst-case executions Informally speaking, due to asynchrony and the possibility of failures, clients always send requests to all servers and in the worst case, all servers respond. Therefore the upper bounds described above are tight.

For the write protocol, the client sends the value to all N nodes in its put phase. So the write communication cost in an execution where at least one write terminates is \(N \log _{2}|\mathcal {V}|\) bits. For the read protocol, consider the following execution, where there is one read operation, and one write operation that is concurrent with this read. We will assume that none of the N servers fail in this execution. Suppose that the writer completes its get phase, and commits to a tag t. Note that t is the highest tag in the system at this point. Suppose that among the N messages that the writer sends in its put phase with the value and tag t, Now the writer begins its put phase where it sends N messages with the value and tag t. At least one of these messages, say the message to server 1, arrives. The remaining messages are delayed, i.e., they are assumed to reach after the portion of the execution segment described here. At this point, the read operation begins and receives (tag, value) pairs from all the N server nodes in its get phase. Of these N messages, at least one message contains the tag t and the corresponding value. Note that t is the highest tag it receives. Therefore, the put phase of the read has to sends N messages with the tag t and the corresponding value - one message to each of the N servers that which responded to the read in the get phase with an older tag.

The read protocol has two phases. The cost of a read operation in an execution is the sum of the communication costs of the messages sent in its get phase and those sent in its put phase. The get phase involves communication of N messages from \(\mathcal {T} \times \mathcal {V}\), one message from each server to the client, and therefore incurs a communication cost of \(N \log _{2}|\mathcal {V}|\) bits provided that every server is active. The put phase involves the communication of a message in \(\mathcal {T} \times \mathcal {V}\) from the client to every server thereby incurring a communication cost of \(N \log _{2}|\mathcal {V}|\) bits as well. Therefore, in any execution where all N servers are active, the communication cost of a read operation is \({2N}\log _{2}|\mathcal {V}|\) bits and therefore the upper bound is tight.

The storage cost is equal to \(N \log _2|\mathcal {V}|\) bits since each of the N servers store exactly one value from \(\mathcal {V}\). \(\square \)

Proof of Theorem 14

Upper bounds: In LDR servers are divided into two groups: directory servers used to manage object metadata, and replication servers used for object replication. Read and write protocols have three sequentially executed phases. The get-metadata and put-metadata phases incur negligible communication cost since only metadata is sent over the message-passing system. In the put phase, the writer sends its messages, each of which is an element from \(\mathcal {T} \times \mathcal {V},\) to \(2f+1\) replica servers and awaits \(f+1\) responses; since the responses have negligible communication cost, this phase incurs a total communication cost of at most \((2f+1)\log _2|\mathcal {V}|\) bits. The read protocol is less taxing, where the reader during the get phase queries \(f+1\) replica servers and in the worst case, all respond with a message containing an element from \(\mathcal {T} \times \mathcal {V}\) thereby incurring a total communication cost of at most \((f+1)\log _2|\mathcal {V}|\) bits.

Worst-case executions It is clear that in every execution where at least one writer terminates, the writer sends out \((2f+1)\) messages to replica servers that contain the value, thus incurring a write communication cost of \((2f+1)\log _{2}|\mathcal {V}|\) bits. Similarly, for a read, in certain executions, all \((f+1)\) replica servers that are selected in the put phase of the read respond to the \(get \) request from the client. So the upper bounds derived above are tight. \(\square \)

Appendix C: Proof of Lemma 1

Proof of property (i): by the definition, each \(Q \in \mathcal {Q}\) has cardinality at least \(\lceil \frac{N+k}{2}\rceil \). Therefore, for \(Q_1, Q_2 \in \mathcal {Q},\) we have

where we have used the fact that \(|Q_1 \cup Q_2| \le N\) in (a).

Proof of property (ii): let \(\mathcal {B}\) be the set of all the server nodes that fail in an execution, where \(|\mathcal {B}| \le f\). We need to show that there exists at least one quorum set \(Q \in \mathcal {Q}\) such that \(Q \subseteq \mathcal {N}-\mathcal {B}\), that is, at least one quorum survives. To show this, because of the definition of our quorum system, it suffices to show that \(|\mathcal {N}-\mathcal {B}| \ge \lceil \frac{N+k}{2}\rceil \). We show this as follows:

where, (b) follows because \(k \le N-2f\) implies that \(f \le \lfloor \frac{N-k}{2}\rfloor \).

Reprints and permissions