Transactors: a programming model for maintaining globally consistent distributed state in unreliable environments

ABSTRACT

We introduce transactors, a fault-tolerant programming model for composing loosely-coupled distributed components running in an unreliable environment such as the internet into systems that reliably maintain globally consistent distributed state. The transactor model incorporates certain elements of traditional transaction processing, but allows these elements to be composed in different ways without the need for central coordination, thus facilitating the study of distributed fault-tolerance from a semantic point of view. We formalize our approach via the τ-calculus, an extended lambda-calculus based on the actor model, and illustrate its usage through a number of examples. The τ-calculus incorporates constructs which distributed processes can use to create globally-consistent checkpoints. We provide an operational semantics for the τ-calculus, and formalize the following safety and liveness properties: first, we show that globally-consistent checkpoints have equivalent execution traces without any node failures or application-level failures, and second, we show that it is possible to reach globally-consistent checkpoints provided that there is some bounded failure-free interval during which checkpointing can occur.

REFERENCES

• 1: Gul Agha, Actors: a model of concurrent computation in distributed systems, MIT Press, Cambridge, MA, 1986
• 2: Gul Agha , Nadeem Jamali , Carlos Varela, Agent naming and coordination: actor based models and infrastructures, Coordination of Internet agents: models, technologies, and applications, Springer-Verlag, London, 2001
• 3: Gul A. Agha , Ian A. Mason , Scott F. Smith , Carolyn L. Talcott, A foundation for actor computation, Journal of Functional Programming, v.7 n.1, p.1-72, January 1997 [doi>10.1017/S095679689700261X]
• 4: M. Berger and K. Honda. The two-phase commitment protocol in an extended pi-calculus. In Prelim. Proc. EXPRESS '00, NS-00-2, pages 105--130. BRICS Notes, 2000.
• 5: Philip A. Bernstein, Middleware: a model for distributed system services, Communications of the ACM, v.39 n.2, p.86-98, Feb. 1996 [doi>10.1145/230798.230809]
• 6: Kenneth P. Birman , Robert V. Renesse , Robbert Van Renesse, Reliable Distributed Computing with the ISIS Toolkit, IEEE Computer Society Press, Los Alamitos, CA, 1994
• 7: Luca Cardelli , Andrew D. Gordon, Mobile Ambients, Proceedings of the First International Conference on Foundations of Software Science and Computation Structure, p.140-155, March 28-April 04, 1998
• 8: T. Chothia and D. Duggan. Abstractions for fault-tolerant global computing. Electronic Notes in Theoretical Computer Science (ENTCS). Foundations of Wide-Area Network Computing (FWAN), 66(3), 2002. Elsevier.
• 9: J. Field and C. Varela. Towards a programming model for building reliable systems with distributed state. Electronic Notes in Theoretical Computer Science (ENTCS). First International Workshop on Foundations of Coordination Languages and Software Architectures (FOCLASA), 68(3), 2003. Elsevier.
• 10: J. Field and C. Varela. Transactors: A programming model for maintaining globally consistent distributed state in unreliable environments. Technical Report 04-15, Department of Computer Science. Rensselaer Polytechnic Institute, Troy, NY, November 2004.
• 11: Cédric Fournet , Georges Gonthier, The reflexive CHAM and the join-calculus, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.372-385, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237805]
• 12: Svend Frølund, Coordinating distributed objects: an actor-based approach to synchronization, MIT Press, Cambridge, MA, 1996
• 13: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 14: Nicholas Haines , Darrell Kindred , J. Gregory Morrisett , Scott M. Nettles , Jeannette M. Wing, Composing first-class transactions, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1719-1736, Nov. 1994 [doi>10.1145/197320.197346]
• 15: C. Hewitt. Viewing control structures as patterns of passing messages. Journal of Artificial Intelligence, 8-3:323--364, June 1977.
• 16: WooYoung Kim , Gul Agha, Efficient support of location transparency in concurrent object-oriented programming languages, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.39-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224297]
• 17: Barbara Liskov, Distributed programming in Argus, Communications of the ACM, v.31 n.3, p.300-312, March 1988 [doi>10.1145/42392.42399]
• 18: Robin Milner , Joachim Parrow , David Walker, A calculus of mobile processes, I, Information and Computation, v.100 n.1, p.1-40, Sept. 1992 [doi>10.1016/0890-5401(92)90008-4]
• 19: A. Spector, R. Pausch, and G. Bruell. Camelot: A flexible, distributed transaction processing system. In Proc. IEEE Computer Society International Conf., pages 432--437, San Francisco, March 1988. IEEE Computer Society Press.
• 20: Carolyn L. Talcott, Composable Semantic Models for Actor Theories, Higher-Order and Symbolic Computation, v.11 n.3, p.281-343, 1998 [doi>10.1023/A:1010042915896]
• 21: Robbert van Renesse , Kenneth P. Birman , Silvano Maffeis, Horus: a flexible group communication system, Communications of the ACM, v.39 n.4, p.76-83, April 1996 [doi>10.1145/227210.227229]
• 22: World Wide Web Consortium. Web services activity statement. http://www.w3.org/2002/ws/, 2002.
• 23: X/Open Company Limited. Distributed transaction processing: The XA specification. X/Open Company Limited, 1991. X/Open CAE Specification XO/CAE/91/300.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Checkpoint/restart; Fault-tolerance

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics; Process models

Keywords:
actor, distributed state, tau-calculus, transactor