hoc networks. In Proceedings of the 17th International
Symposium on Distributed Computing (2003), 306–320.
17. Dutta, P., Guerraoui, R., Levy, R.R. and Vukolić, M.
Fast access to distributed atomic memory. SIAM J.
Comput. 39, 8 (Dec. 2010), 3752–3783.
18. Fekete, A., Lynch, N. and Shvartsman, A. Specifying
and using a partitionable group communication service.
ACM Trans. Comput. Syst. 19, 2 (2001), 171–216.
19. Fischer, M.J., Lynch, N.A. and Paterson, M.S.
Impossibility of distributed consensus with one faulty
process. JACM 32, 2 (1985), 374-382.
20. Georgiou, C., Musial, P.M. and Shvartsman, A.A.
Developing a consistent domain-oriented distributed
object service. IEEE Transactions of Parallel and
Distributed Systems 20, 11 (2009), 1567–1585.
21. Georgiou, C., Musial, P.M. and Shvartsman, A. A. Fault-tolerant semifast implementations of atomic read/write
registers. J. Parallel and Distributed Computing 69, 1
(Jan. 2009), 62–79.
22. Ghemawat, S., Gobioff, H. and Leung, S.- T. The Google
File System. In Proceedings of the 19th ACM Symposium
on Operating Systems Principles (2003), 29–43.
23. Gilbert, S. and Lynch, N. Brewer’s conjecture and the
feasibility of consistent, available, partition-tolerant
web services. SIGACT News 33 (June 2002), 51–59.
24. Gilbert, S., Lynch, N. and Shvartsman, A. RAMBO: A
robust, reconfigurable atomic memory service for
dynamic networks. Distributed Computing 23, 4, (Dec.
25. Herlihy, M.P. and Wing, J.M. Linearizability: A correctness condition for concurrent objects. ACM Trans.
Programming Languages and Systems 12, 3 (July
26. Imielin´ski, T. and Navas, J.C. GPS-based geographic
addressing, routing, and resource discovery. Commun.
ACM 42, 4 (Apr. 1999), 86–92.
27. Lakshman, A. and Malik, P. Cassandra: A decentralized
structured storage system. SIGOPS Oper. Syst. Rev.
44, 2 (Apr. 2010), 35–40.
28. Lamport, L. On interprocess communication. Part I: Basic
formalism. Distributed Computing 2, 1 (1986), 77–85.
29. Lamport, L. The part-time parliament. ACM Trans.
Comput. Syst. 16, 2 (1998), 133–169.
30. Liskov, B. The power of abstraction. In Proceedings of
the 24th Int-l Symposium Distributed Computing. N. A.
Lynch and A.A. Shvartsman, Eds. LNCS, vol. 6343,
31. Loui, M. C. and Abu-Amara, H. H. Memory requirements
for agreement among unreliable asynchronous
processes. In Parallel and Distributed Computing, Vol
4 of Advances in Computing Research. F.P. Preparata,
Ed. JAI Press, Greenwich, Conn., 1987, 163–183.
32. Lynch, N. and Shvartsman, A. Robust emulation of
shared memory using dynamic quorum-acknowledged
broadcasts. In Symposium on Fault-Tolerant
Computing. IEEE, 1997, 272–281.
33. Lynch, N.A. Distributed Algorithms. Morgan Kaufmann
Publishers Inc., 1996.
34. Martin, J.-P. and Alvisi, L. A framework for dynamic
byzantine storage. In Proc. Intl. Conf. on Dependable
Systems and Networks, 2004.
35. Rodrigues, R., Liskov, B., Chen, K., Liskov, M. and
Schultz, D. Automatic reconfiguration for large-scale
reliable storage systems. IEEE Trans. on Dependable
and Secure Computing 9, 2 (2012), 145–158.
36. Saito, Y., Frølund, S., Veitch, A., Merchant, A. and
Spence, S. Fab: Building distributed enterprise disk
arrays from commodity components. SIGARCH
Comput. Archit. News 32, 5 (Oct. 2004), 48–58.
37. Shraer, A. Martin, J.-P., Malkhi, D. and Keidar, I. Data-centric reconfiguration with network-attached disks. In
Proceedings of the 4th Int’l Workshop on Large Scale
Distributed Systems and Middleware (2010), ACM, 22–26.
38. Vukolić, M. Quorum systems: With applications
to storage and consensus. Synthesis Lectures on
Distributed Computing Theory 3, (Jan. 3, 2012). 1–146.
Peter Musial ( firstname.lastname@example.org) is a principal
software engineer at EMC and a CSAIL affiliate at MIT,
Nicolas Nicolaou ( email@example.com) is a visiting
lecturer in the Computer Science Department of
University of Cyprus, Nicosia, Cyprus.
Alexander A. Shvartsman ( firstname.lastname@example.org) is a
professor of computer science and engineering at the
University of Connecticut, Storrs, CT.
© 2014 ACM 0001-0782/14/06 $15.00
of replicas is small, they may cause undue overheads when nodes continue
joining and leaving the service even
though some core set of hosts is stable
and sufficient for providing good service. Another approach is to leave the
decision for when to reconfigure to another distributed service that monitors
the performance of the memory system
and decides when to reconfigure based
on these observations and on speculative forecasts. This is a more complicated solution, but it has the potential
of providing superior quality of service.
Additional consideration is selecting
a suitable set of hosts. Just because a
node is interested in serving as a replica host does not mean its wish must be
granted. Here, the external service that
decides when to reconfigure can also
decide on the target set of nodes. Note
that no agreement on the target set is
required—all memory services are able
to deal with the situations when several
target sets are proposed.
The dynamic atomic shared memory services guarantee consistency in
all executions, regardless of the magnitude or frequency of replica host
failures. Termination of read and write
operations, however, is conditioned on
restricting failures. For static systems,
generally this restriction can be easily
formulated: here, any minority subset
of hosts is allowed to fail. For dynamic systems the constraints on failure
patterns are much more involved and
depend on the specific algorithmic approaches; the reader is referred to the
cited articles for additional details.
With the advent of Cloud services,
distributed storage services are bound
to continue attract attention. The tech-
nical challenges and performance
overheads may be the reasons why the
existing distributed storage solutions
shy away from atomic consistency guar-
antees. Commercial solutions, such as
Google’s File System (GFS), 22 Amazon’s
Dynamo, 15 and Facebook’s Cassandra, 28
provide less-than-intuitive, unproved
guarantees. The concepts discussed
in this survey are echoed in the design
decisions of production systems. For
instance, consensus is used in GFS22 to
ensure agreement on system configu-
ration as it is done in Rambo; global
time is used in Spanner13 as it is done
in GeoQuorums; replica access pro-
tocols in Dynamo15 use quorums as in
some approaches surveyed here. These
examples provide motivation for pursu-
ing rigorous algorithmic approaches in
the study of consistent data services for
dynamic networked systems.
Consistent storage systems continues to be an area of active research and
advanced development, and there are
good reasons to believe that as high-performance dynamic memory systems
with superior fault-tolerance become
available, they will play a significant role
in the construction of sophisticated
distributed applications. The demand
for implementations providing atomic
read/write memory will ultimately be
driven by the needs of distributed applications that require provable consistency and performance guarantees.
This work was supported in part by the
NSF award 1017232. We thank Jennifer
Welch and the anonymous reviewers
for numerous insightful comments.
1. Aguilera, M., Keidar, I., Martin, J.-P. and Shraer, A.
Reconfiguring replicated atomic storage: A tutorial.
Bulletin of the EATCS 102 (Oct. 2010), 84–108.
2. Aguilera, M.K., Keidar, I., Malkhi, D. and Shraer, A.
Dynamic atomic storage without consensus. JACM 58
(Apr. 2011), 7:1–7: 32.
3. Attiya, H., Bar-Noy, A. and Dolev, D. Sharing memory
robustly in message-passing systems. JACM 42, 1
(Jan. 1995), 124–142.
4. Attiya, H. and Welch, J.L. Sequential consistency
versus linearizability. ACM Trans. Comput. Syst. 12, 2
(May 1994), 91–122.
5. Birman, K. A history of the virtual synchrony
replication model. Replication: Theory and Practice,
LNCS vol. 5959 (2010), 91–120.
6. Birman, K., Malkhi, D. and Renesse, R.V. Virtually
synchronous methodology for dynamic service
replication. Technical report, MSR-TR-2010-151,
Microsoft Research, 2010.
7. Brewer, E.A. Towards robust distributed systems,
8. Brewer, E.A. Pushing the cap: Strategies for
consistency and availability. IEEE Computer 45, 2
9. Calder, B. et al. Windows azure storage: A highly
available cloud storage service with strong
consistency. In Proceedings of SOSP ‘ 11 (Oct 23-26,
10. Chandra, T.D., Hadzilacos, V. and Toueg, S. The
weakest failure detector for solving consensus. JACM
11. Chockler, G., Gilbert, S., Gramoli, V., Musial, P.M. and
Shvartsman, A.A. Reconfigurable distributed storage
for dynamic networks. J. Parallel and Distributed
Computing 69, 1 (2009), 100–116.
12. Chockler, G., Guerraoui, R., Keidar, I. and Vukolić, M.
Reliable distributed storage. IEEE Computer, 2008.
13. Corbett, J.C. et al. Spanner: Google’s globally
distributed database. In Proceedings of the 10th
USENIX Symp. On Operating Sys. Design and
Implementation (2012), 251–264.
14. De Prisco, R., Fekete, A., Lynch, N. A. and Shvartsman,
A.A. A dynamic primary configuration group
communication service. In Proceedings of the 13th
Int-l Symposium on Distributed Computing. Springer-Verlag, 1999, 64–78.
15. DeCandia, G. et al. Dynamo: Amazon’s highly available
key-value store. In Proceedings of SIGOPS Oper. Syst.
Rev. 41, 6 (Oct. 2007), 205–220.
16. Dolev, S., Gilbert, S., Lynch, N., Shvartsman, A. and Welch,
J. GeoQuorums: Implementing atomic memory in ad