Optimal message-driven implementations of omega with mute processes

ABSTRACT

We investigate the complexity of algorithms in message-driven models. In such models, events in the computation can only be caused by message receptions, but not by the passage of time. Hutle and Widder [2005a] have shown that there is no deterministic message-driven self-stabilizing implementation of the eventually strong failure detector and thus Ω in systems with uncertainty in message delays and channels of unknown capacity using only bounded space. Under stronger assumptions it was shown that even the eventually perfect failure detector can be implemented in message-driven systems consisting of at least f + 2 processes (f being the upper bound on the number of processes that crash during an execution).

In this article we show that f + 2 is in fact a lower bound in message-driven systems, even if nonstabilizing algorithms are considered. This contrasts time-driven models where f + 1 is sufficient for failure detector implementations.

Moreover, we investigate algorithms where not all processes send message, that is, are active, but some (in a predetermined set) remain passive. Here, we show that the f + 2 processes required for message-driven systems must be active, while in time-driven systems it suffices that f processes are active.

We also provide message-driven implementations of Ω. Our algorithms are efficient in the sense that not all processes have to send messages forever, which is an improvement to previous message-driven failure detector implementations.

REFERENCES

• 1: Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, On implementing omega with weak reliability and synchrony assumptions, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.306-314, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872081]
• 2: Marcos K. Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, Communication-efficient leader election and consensus with limited link synchrony, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011816]
• 3: Beauquier, J. and Kekkonen-Moneta, S. 1997. Fault-tolerance and self-stabilization: Impossibility results and solutions using self-stabilizing failure detectors. Int. J. Syst. Sci. 28, 11, 1177--1187.
• 4: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Journal of the ACM (JACM), v.43 n.4, p.685-722, July 1996 [doi>10.1145/234533.234549]
• 5: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 6: Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
• 7: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 8: Jo C. Ebergen, A formal approach to designing delay-insensitive circuits, Distributed Computing, v.5 n.3, p.107-119, December 1991 [doi>10.1007/BF02252954]
• 9: Einstein, A. 1905. Zur Elektrodynamik bewegter Körper. Annalen der Physik 322, 10, 891--921.
• 10: Christof Fetzer , Ulrich Schmid , Martin Susskraut, On the Possibility of Consensus in Asynchronous Systems with Finite Average Response Times, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.271-280, June 06-10, 2005 [doi>10.1109/ICDCS.2005.57]
• 11: Fischer, M. and Lamport, L. 1982. Byzantine generals and transaction commit protocols. Tech. rep. 62, SRI International.
• 12: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 13: Matthias Fugger , Ulrich Schmid , Gottfried Fuchs , Gerald Kempf, Fault-Tolerant Distributed Clock Generation in VLSI Systems-on-Chip, Proceedings of the Sixth European Dependable Computing Conference, p.87-96, October 18-20, 2006 [doi>10.1109/EDCC.2006.11]
• 14: Gärtner, F. C. and Pleisch, S. 2001. (Im)possibilities of predicate detection in crash-affected systems using interrupt-style failure detectors. In Brief Announcements—15th International Symposium on DIStributed Computing (DISC'01), J. Welch, Ed. Tech. rep. TR-01-7. Departamento de Informática, Faculdade de Ciências da Universidade de Lisboa, Lisboa, Portugal. 7--12. http://www.di.fc.ul.pt/publications/di-fcul-tr-01-7_document.pdf.
• 15: Rachid Guerraoui , André Schiper, "Gamma-Accurate" Failure Detectors, Proceedings of the 10th International Workshop on Distributed Algorithms, p.269-286, October 09-11, 1996
• 16: Hermant, J.-F. and Widder, J. 2005. Implementing reliable distributed real-time systems with the Θ-model. In Proceedings of the 9th International Conference on Principles of Distributed Systems (OPODIS'05). Lecture Notes in Computer Science, vol. 3974. Springer Verlag, 334--350.
• 17: Hutle, M., Malkhi, D., Schmid, U., and Zhou, L. 2006. Brief announcement: Chasing the weakest system model for implementing omega and consensus. In Proceedings of the 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'06). Lecture Notes in Computer Science, vol. 9280. Springer Verlag, 576--577.
• 18: Hutle, M., Malkhi, D., Schmid, U., and Zhou, L. 2008. Chasing the weakest system model for implementing omega and consensus. IEEE Trans. Depend. Secure Comput. To appear.
• 19: Martin Hutle , Josef Widder, Brief announcement: on the possibility and the impossibility of message-driven self-stabilizing failure detection, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073852]
• 20: Hutle, M. and Widder, J. 2005b. Self-stabilizing failure detector algorithms. In Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Networks (PDCN'05). IASTED/ACTA Press, 485--490.
• 21: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 22: Le Lann, G. and Schmid, U. 2003. How to implement a timer-free perfect failure detector in partially synchronous systems. Tech. rep. 183/1-127, Department of Automation, Technische Universität Wien.
• 23: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 24: Malkhi, D., Oprea, F., and Zhou, L. 2005. Ω meets paxos: Leader election and stability without eventual timely links. In Proceedings of the 19th Symposium on Distributed Computing (DISC'05). Lecture Notes in Computer Science, vol. 3724. Springer Verlag, 199--213.
• 25: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 26: Peter Robinson , Ulrich Schmid, The asynchronous bounded-cycle model, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400815]
• 27: Nicola Santoro , Peter Widmayer, Time is Not a Healer, Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science, p.304-313, February 16-18, 1989
• 28: T. K. Srikanth , Sam Toueg, Optimal clock synchronization, Journal of the ACM (JACM), v.34 n.3, p.626-645, July 1987 [doi>10.1145/28869.28876]
• 29: Widder, J. 2003. Booting clock synchronization in partially synchronous systems. In Proceedings of the 17th International Symposium on Distributed Computing (DISC'03). Lecture Notes in Computer Science, vol. 2848. Springer Verlag, 121--135.
• 30: Widder, J. 2004. Distributed computing in the presence of bounded asynchrony. Ph.D. thesis, Vienna University of Technology, Fakultät für Informatik.
• 31: Widder, J., Le Lann, G., and Schmid, U. 2005. Failure detection with booting in partially synchronous systems. In Proceedings of the 5th European Dependable Computing Conference (EDCC-5). Lecture Notes in Computer Science, vol. 3463. Springer Verlag, 20--37.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Reliability, Theory

Keywords:
Fault tolerance, lower bound, message-driven distributed algorithm, unreliable failure detectors