The Weakest Failure Detector for Eventual Consistency

ABSTRACT

In its classical form, a consistent replicated service requires all replicas to witness the same evolution of the service state. Assuming a message-passing environment with a majority of correct processes, the necessary and sufficient information about failures for implementing a general state machine replication scheme ensuring consistency is captured by the Ω failure detector.

This paper shows that in such a message-passing environment, Ω is also the weakest failure detector to implement an eventually consistent replicated service, where replicas are expected to agree on the evolution of the service state only after some (a priori unknown) time.

In fact, we show that Ω is the weakest to implement eventual consistency in any message-passing environment, i.e., under any assumption on when and where failures might occur. Ensuring (strong) consistency in any environment requires, in addition to Ω, the quorum failure detector ∑. Our paper thus captures, for the first time, an exact computational difference between building a replicated state machine that ensures consistency and one that only ensures eventual consistency.

References

1. E. A. Brewer. Towards robust distributed systems (abstract). In Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '00, pages 7--, 2000.
2. T. D. Chandra, V. Hadzilacos, and S. Toueg. The weakest failure detector for solving consensus. J. ACM, 43(4):685--722, July 1996.
3. T. D. Chandra and S. Toueg. Unreliable failure detectors for reliable distributed systems. J. ACM, 43(2):225--267, Mar. 1996.
4. F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber. Bigtable: A distributed storage system for structured data. ACM Trans. Comput. Syst., 26(2):4:1--4:26, June 2008.
5. B. Charron-Bost and G. Tel. Approximation d'une borne inférieure répartie. Technical Report LIX/RR/94/06, Laboratoire d'Informatique LIX, École Polytechnique, Sept. 1994.
6. B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. Pnuts: Yahoo!'s hosted data serving platform. Proc. VLDB Endow., 1(2):1277--1288, Aug. 2008.
7. G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon's highly available key-value store. In Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles, SOSP '07, pages 205--220, New York, NY, USA, 2007. ACM.
8. C. Delporte-Gallet, H. Fauconnier, and R. Guerraoui. Tight failure detection bounds on atomic object implementations. J. ACM, 57(4), 2010.
9. S. Dolev, R. I. Kat, and E. M. Schiller. When consensus meets self-stabilization. Journal of Computer and System Sciences, 76(8):884 -- 900, 2010.
10. S. Dubois, R. Guerraoui, P. Kuznetsov, F. Petit, and P. Sens. The weakest failure detector for eventual consistency. CoRR, abs/X.X, 2015.
11. A. Fekete, D. Gupta, V. Luchangco, N. Lynch, and A. Shvartsman. Eventually-serializable data services. In Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '96, pages 300--309, New York, NY, USA, 1996. ACM.
12. M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374--382, Apr. 1985.
13. F. C. Freiling, R. Guerraoui, and P. Kuznetsov. The failure detector abstraction. ACM Comput. Surv., 43(2):9:1--9:40, Feb. 2011.
14. S. Gilbert and N. Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 33(2):51--59, June 2002.
15. R. Guerraoui, V. Hadzilacos, P. Kuznetsov, and S. Toueg. The weakest failure detectors to solve quittable consensus and nonblocking atomic commit. SIAM J. Comput., 41(6):1343--1379, 2012.
16. R. Guerraoui and E. Ruppert. A paradox of eventual linearizability in shared memory. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC '14, pages 40--49, 2014.
17. V. Hadzilacos and S. Toueg. A modular approach to fault-tolerant broadcasts and related problems. Technical Report TR 94--1425, Department of Computer Science, Cornell University, May 1994.
18. P. Jayanti and S. Toueg. Every problem has a weakest failure detector. In PODC, pages 75--84, 2008.
19. F. Kuhn, Y. Moses, and R. Oshman. Coordinated consensus in dynamic networks. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 1--10. ACM, 2011.
20. A. Lakshman and P. Malik. Cassandra: A decentralized structured storage system. SIGOPS Oper. Syst. Rev., 44(2):35--40, Apr. 2010.
21. L. Lamport. Proving the correctness of multiprocessor programs. Transactions on software engineering, 3(2):125--143, Mar. 1977.
22. L. Lamport. The Part-Time parliament. ACM Transactions on Computer Systems, 16(2):133--169, May 1998.
23. L. Lamport. Lower bounds for asynchronous consensus. Distributed Computing, 19(2):104--125, 2006.
24. A. Mostefaoui, M. Raynal, and F. Tronel. From binary consensus to multivalued consensus in asynchronous message-passing systems. Inf. Process. Lett., 73(5--6):207--212, Mar. 2000.
25. Y. Saito and M. Shapiro. Optimistic replication. ACM Comput. Surv., 37(1):42--81, Mar. 2005.
26. F. B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys, 22(4):299--319, Dec. 1990.
27. M. Serafini, D. Dobre, M. Majuntke, P. Bokor, and N. Suri. Eventually linearizable shared objects. In A. W. Richa and R. Guerraoui, editors, Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, pages 95--104. ACM, 2010.
28. A. Singh, P. Fonseca, P. Kuznetsov, R. Rodrigues, and P. Maniatis. Zeno: Eventually consistent byzantine-fault tolerance. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, NSDI'09, pages 169--184, Berkeley, CA, USA, 2009. USENIX Association.
29. W. Vogels. Eventually consistent. Commun. ACM, 52(1):40--44, Jan. 2009.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

• Theory of computation

  • Logic

  • Models of computation