Abstract
It is well known that in an asynchronous message-passing system, one can emulate an atomic register providing that more than half of the processes are non-faulty. By contrast, when a majority of the processes may fail, simulating atomic register is not possible. This paper investigates weak variants of atomic registers that can be simulated tolerating a majority of processes failures. Specifically, the paper introduces a new class of registers, called α-register and shows how to emulate them.
For atomic registers, a read operation returns the last written value when there is no concurrent write operations. α-registers generalize atomic registers in the following sense: In any interval I, at most α values written before I are returned by the read operations in I. A simulation of an α-register tolerating f failures in a n-processes system is presented for α = 2M − 1, where M = max (1,2f − n + 2). The simulation is optimal up to a constant multiplicative factor: the paper establishes that α-registers cannot be simulated tolerating f failures if α ≤ M.
This work is supported in part by the ANR project DISPLEXITY.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abraham, I., Malkhi, D.: Probabilistic quorums for dynamic systems. Distributed Computing 18(2), 113–124 (2005)
Afek, Y., Gafni, E., Rajsbaum, S., Raynal, M., Travers, C.: The k-simultaneous consensus problem. Distributed Computing 22(3), 185–195 (2010)
Aguilera, M.K., Keidar, I., Malkhi, D., Shraer, A.: Dynamic atomic storage without consensus. J. ACM 58(2), 7 (2011)
Alon, N., Attiya, H., Dolev, S., Dubois, S., Potop-Butucaru, M., Tixeuil, S.: Pragmatic self-stabilization of atomic memory in message-passing systems. In: Défago, X., Petit, F., Villain, V. (eds.) SSS 2011. LNCS, vol. 6976, pp. 19–31. Springer, Heidelberg (2011)
Attiya, H., Bar-Noy, A., Dolev, D.: Sharing memory robustly in message-passing systems. J. ACM 42(1), 124–142 (1995)
Attiya, H., Welch, J.: Distributed Computing. Wiley (2004)
Bonnin, D., Travers, C.: α-register. Technical report hal#00863060 (2013), http://hal.inria.fr/hal-00863060/PDF/
Bouzid, Z., Travers, C.: (anti −Ωx ×Σ z )-based k-set agreement algorithms. In: Lu, C., Masuzawa, T., Mosbah, M. (eds.) OPODIS 2010. LNCS, vol. 6490, pp. 189–204. Springer, Heidelberg (2010)
Bouzid, Z., Travers, C.: Parallel consensus is harder than set agreement in message passing. In: ICDCS. IEEE Computer Society (2013)
Apache cassandra, http://cassandra.apache.org/
Chandra, T., Hadzilacos, V., Toueg, S.: The weakest failure detector for solving consensus. J. ACM 43(4), 685–722 (1996)
Chaudhuri, S.: More choices allow more faults: set consensus problems in totally asynchronous systems. Inf. Comput. 105(1), 132–158 (1993)
DeCandia, G., et al.: Dynamo: amazon’s highly available key-value store. In: SOSP, pp. 205–220. ACM (2007)
Dolev, S., Dubois, S., Gradinariu Potop-Butucaru, M., Tixeuil, S.: Crash resilient and pseudo-stabilizing atomic registers. In: Baldoni, R., Flocchini, P., Binoy, R. (eds.) OPODIS 2012. LNCS, vol. 7702, pp. 135–150. Springer, Heidelberg (2012)
Fekete, A., Gupta, D., Luchangco, V., Lynch, N.A., Shvartsman, A.A.: Eventually-serializable data services. Theor. Comput. Sci. 220(1), 113–156 (1999)
Friedman, R., Kliot, G., Avin, C.: Probabilistic quorum systems in wireless ad hoc networks. ACM Trans. Comput. Syst. 28(3) (2010)
Friedman, R., Raynal, M., Travers, C.: Two abstractions for implementing atomic objects in dynamic systems. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds.) OPODIS 2005. LNCS, vol. 3974, pp. 73–87. Springer, Heidelberg (2006)
Gafni, E.: The extended bg-simulation and the characterization of t-resiliency. In: STOC, pp. 85–92. ACM (2009)
Gilbert, S., Lynch, N.A.: Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News 33(2), 51–59 (2002)
Gilbert, S., Lynch, N.A., Shvartsman, A.A.: Rambo: a robust, reconfigurable atomic memory service for dynamic networks. Distributed Computing 23(4), 225–272 (2010)
Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858–923 (1999)
Lamport, L.: On interprocess communication. Distributed Computing 1(2), 77–101 (1986)
Malkhi, D., Reiter, M.K., Wool, A., Wright, R.N.: Probabilistic quorum systems. Inf. Comput. 170(2), 184–206 (2001)
Terry, D.B., Demers, A.J., Petersen, K., Spreitzer, M., Theimer, M., Welch, B.B.: Session guarantees for weakly consistent replicated data. In: PDIS, pp. 140–149. IEEE Computer Society (1994)
Yu, H.: Overcoming the majority barrier in large-scale systems. In: Fich, F.E. (ed.) DISC 2003. LNCS, vol. 2848, pp. 352–366. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Bonnin, D., Travers, C. (2013). α-Register. In: Baldoni, R., Nisse, N., van Steen, M. (eds) Principles of Distributed Systems. OPODIS 2013. Lecture Notes in Computer Science, vol 8304. Springer, Cham. https://doi.org/10.1007/978-3-319-03850-6_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-03850-6_5
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03849-0
Online ISBN: 978-3-319-03850-6
eBook Packages: Computer ScienceComputer Science (R0)