Travelling through wormholes: a new look at distributed systems models

Abstract

The evolution of distributed computing and applications has put new challenges on models, architectures and systems. To name just one, 'reconciling uncertainty with predictability' is required by today's simultaneous pressure on increasing the quality of service of applications, and on degrading the assurance given by the infrastructure.This challenge can be mapped onto more than one facet, such as time or security or others. In this paper we explore the time facet, reviewing past and present of distributed systems models, and making the case for the use of hybrid (vs. homogeneous) models, as a key to overcoming some of the difficulties faced when asynchronous models (uncertainty) meet timing specifications (predictability). The Wormholes paradigm is described as the first experiment with hybrid distributed systems models.

References

1. M. Aguilera, G. Le Lann, and S. Toueg. On the impact of fast failure detectors on real-time fault-tolerant systems. In Proc. of DISC 2002, October 2002.]]
2. E. Anceaume, B. Charron-Bost, P. Minet, and S. Toueg. On the formal specification of group membership services. Technical Report RR-2695, INRIA, Rocquencourt, France, November 1995.]]
3. M. Ben-Or. Another advantage of free choice: Completely asynchronous agreement protocols. In Proceedings of the 2nd ACM Symposium on Principles of Distributed Computing, pages 27--30, August 1983.]]
4. A. Casimiro, P. Martins, and P. Veríssimo. How to build a Timely Computing Base using Real-Time Linux. In Proceedings of the IEEE International Workshop on Factory Communication Systems, pages 127--134, September 2000.]]
5. M. Castro and B. Liskov. Practical Byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4):398--461, November 2002.]]
6. T. Chandra, V. Hadzilacos, S. Toueg, and B. Charron-Bost. On the impossibility of group membership. In Proceedings of the 15th ACM Symposium on Principles of Distributed Computing, pages 322--330, May 1996.]]
7. T. Chandra and S. Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, 43(2):225--267, March 1996.]]
8. F. Christian and C. Fetzer. The timed asynchronous system model. In Proceedings of the 28th IEEE International Symposium on Fault-Tolerant Computing, pages 140--149, 1998.]]
9. M. Correia, N. F. Neves, L. C. Lung, and P. Veríssimo. Low complexity Byzantine-resilient consensus. Distributed Computing, 17(3):237--249, 2005.]]
10. M. Correia, P. Veríssimo, and N. F. Neves. The design of a COTS real-time distributed security kernel. In Proceedings of the Fourth European Dependable Computing Conference, pages 234--252, October 2002.]]
11. C. Delporte-Gallet, H. Fauconnier, and R. Guerraoui. A realistic look at failure detectors. In Proceedings of the International Conference on Dependable Systems and Networks, pages 213--222, Washington, USA, June 2002.]]
12. D. Dolev, C. Dwork, and L. Stockmeyer. On the minimal synchronism needed for distributed consensus. Journal of the ACM, 34(1):77--97, January 1987.]]
13. C. Dwork, N. Lynch, and L. Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288--323, April 1988.]]
14. Christof Fetzer. Perfect failure detection in timed asynchronous systems. IEEE Trans. Comput., 52(2):99--112, 2003.]]
15. M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374--382, April 1985.]]
16. R. Friedman, A. Moustefaoui, S. Rajsbaum, and M. Raynal. Error correcting codes: A future direction to solve distributed agreement problems? In International Workshop on Future Directions of Distributed Computing, FuDiCo, June 2002.]]
17. Roy Friedman, Achour Mostéfaoui, and Michel Raynal. Building and using quorums despite any number of process crashes. In 5th European Dependable Computing Conference (EDCC'05), Budapest, Hungary.]]
18. J.M. Helary, M. Hurfin, A. Mostefaoui, M. Raynal, and Tronel F. Computing global functions on asynchronous distributed systems with perfect failure detectors. IEEE Transactions on Parallel and Distributed Systems, 11(9), September 2000.]]
19. I. Keidar and S. Rajsbaum. On the cost of fault-tolerant consensus when there are no faults - a tutorial. SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory), 32(2):45--63, 2001. Preliminary version, MIT Technical Report MIT-LCS-TR-821, May 24, 2001.]]
20. F. Meyer and D. Pradhan. Consensus with dual failure modes. In Proceedings of the 17th IEEE International Symposium on Fault-Tolerant Computing, pages 214--222, July 1987.]]
21. A. Mostéfaoui, E. Mourgaya, and M. Raynal. Asynchronous implementation of failure detectors. In Int. IEEE/IFIP Conference on Dependable Systems and Networks (DSN'03), San Francisco (USA).]]
22. N. F. Neves, M. Correia, and P. Veríssimo. Solving vector consensus with a wormhole. IEEE Transactions on Parallel and Distributed Systems, 16(12):1120--1131, December 2005.]]
23. D. Powell. Fault assumptions and assumption coverage. In Proceedings of the 22nd IEEE International Symposium of Fault-Tolerant Computing, July 1992.]]
24. D. Powell, D. Seaton, G. Bonn, P. Veríssimo, and F. Waeselynk. The Delta-4 approach to dependability in open distributed computing systems. In Proceedings of the 18th IEEE International Symposium on Fault-Tolerant Computing, June 1988.]]
25. M. Raynal. Short introduction to failure detectors for asynchronous distributed systems. SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory), 36(1):53--70, 2005.]]
26. Nicola Santoro and Peter Widmayer. Majority and unanimity in synchronous networks with ubiquitous dynamic faults. In SIROCCO, pages 262--276, 2005.]]
27. P. Sousa, N. F. Neves, and P. Verissimo. How resilient are distributed f fault/intrusion-tolerant systems? In Proceedings of the IEEE International Conference on Dependable Systems and Networks, June 2005.]]
28. Jan van Leeuwen and Jir Wiedermann. Beyond the turing limit: Evolving interactive systems. In Leszek Pacholski and Peter Ruzicka, editors, SOFSEM: Theory and Practice of Informatics, 28th Conference on Current Trends in Theory and Practice of Informatics, volume 2234 of Lecture Notes in Computer Science, pages 90--109, Piestany, Slovak Republic, 2001. Springer.]]
29. P. Veríssimo. Uncertainty and predictability: Can they be reconciled? In Future Directions in Distributed Computing, volume 2584 of Lecture Notes in Computer Science, pages 108--113. Springer-Verlag, 2003.]]
30. P. Veríssimo and A. Casimiro. The Timely Computing Base model and architecture. IEEE Transactions on Computers, 51(8):916--930, August 2002. Supersedes Tech. Rep. DI/FCUL TR-99-2, Dpt. of Informatics, University of Lisboa, May 1999.]]
31. P. Veríssimo, A. Casimiro, and C. Fetzer. The Timely Computing Base: Timely actions in the presence of uncertain timeliness. In Proceedings of the International Conference on Dependable Systems and Networks, pages 533--542, June 2000.]]
32. P. Veríssimo and L. Rodrigues. Distributed Systems for System Architects. Kluwer Academic Publishers, 2001.]]
33. P. Veríssimo, L. Rodrigues, and A. Casimiro. Cesiumspray: a precise and accurate global clock service for large-scale systems. Journal of Real-Time Systems, 12(3):243--294, May 1997.]]
34. C. Walter, N. Suri, and M. Hugue. Continual on-line diagnosis of hybrid faults. In Proceedings of the 4th IFIP International Working Conference on Dependable Computing for Critical Applications, 1994.]]
35. L. Zhou, F. Schneider, and R. van Renesse. COCA: A secure distributed on-line certification authority. ACM Transactions on Computer Systems, 20(4):329--368, November 2002.]]

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• General and reference

  • Cross-computing tools and techniques

    • Design

• Information systems

  • Information retrieval

    • Evaluation of retrieval results

    • Search engine architectures and scalability

      • Distributed retrieval

      • Peer-to-peer retrieval

  • Information storage systems

    • Storage architectures

      • Distributed storage

  • Information systems applications

• Software and its engineering

  • Software creation and management

    • Designing software

  • Software organization and properties

    • Contextual software domains

      • Operating systems

    • Software system structures

      • Distributed systems organizing principles