Efficient logic variables for distributed computing

ABSTRACT

We define a practical algorithm for distrubuted rational tree unification and prove its correctness in both the off-line and on-line cases. We derive the distributed algorithm from a centralized one, showing clearly the trade-offs between local and distributed execution. The algorithm is used to realize logic variables in the Mozart Programming System, which implements the Oz language (see http://www/mozart-oz.org). Oz appears to the programmer as a concurrent object-oriented language with dataflow synchronization. Logic variables implement the dataflow behavior. We show that lohgic variables can easily be added to the more restricted models of Java and ML, thus providing an alternative way to do concurent programming in these languages. We present common distributed programming idioms in a network-transparent way using logic variables. We show that in common cases the algorithm maintains the same message latency as explicit message passing. In addition, it is able to handle uncommon cases that arise from the properties of latency tolerance and third-party independence. This is evidence that using logic variables in distributed computing is beneficial at both the system and language levels. At the system level, they improve latency tolerance and third-party independence. At the language level, they help make network-transparent distribution practical.

REFERENCES

• 1: M. W. Alford , J. P. Ansart , G. Hommel , L. Lamport , B. Liskov , G. P. Mullery , F. B. Schneider, Distributed systems: methods and tools for specification. An advanced course, Springer-Verlag New York, Inc., New York, NY, 1985
• 2: ALOUINI, I. AND VAN ROY, P. 1999. Le protocole r6parti de Distributed Oz (in French). In Colloque Francophone sur l'Ingdnierie des Protocoles (CFIP 99). 283-298.
• 3: Joe Armstrong , Robert Virding , Claes Wikström , Mike Williams, Concurrent programming in ERLANG (2nd ed.), Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1996
• 4: ARVIND AND THOMAS, R. E. 1980. I-Structures: An efficient data type for functional languages. Tech. Rep. 210, MIT, Laboratory for Computer Science.
• 5: Henri E. Bal , Jennifer G. Steiner , Andrew S. Tanenbaum, Programming languages for distributed computing systems, ACM Computing Surveys (CSUR), v.21 n.3, p.261-322, Sep. 1989 [doi>10.1145/72551.72552]
• 6: BRAND, P., VAN ROY, P., COLLET, R., AND I~LINTSKOG, E. 1999. Formal definition and correctness of a reliable mobile-state protocol for constructing fault-tolerant applications. In preparation.
• 7: CARDELLI, L. 1995. A language with distributed scope. ACM Trans. Comput. Syst. 8, 1 (Jan.), 27-59.
• 8: Randy Chow , Yuen-Chien Chow, Distributed Operating Systems and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 9: COLMERAUER, A. 1982. Prolog and Infinite Trees. Academic Press. In Logic Programming, Keith L. Clark and Sten-Ake Tarnlund, eds.
• 10: COURCELLE, B. 1983. Fundamental properties of infinite trees. Theoretical Computer Science 25, 95-169.
• 11: DFKI Oz 1998. DFKI Oz version 2.0. Available at http://www.ps.uni-sb.de.
• 12: DIAZ, M., RUBIO, B., AND TROYA, J. M. 1997. DRL: A distributed real-time logic language. Comput. Lang. 23, 2-4, 87-120.
• 13: DUCHIER, D., KORNSTAEDT, L., SCHULTE, C., AND SMOLKA, G. 1998. A Higher-order Module Discipline with Separate Compilation, Dynamic Linking, and Pickling. Tech. rep., Programming Systems Lab, DFKI and Universitgt des Saarlandes. DRAFT.
• 14: FOSTER, I. 1988. Parallel implementation of Parlog. In International Conference on Parallel Processing. IEEE Computer Society, 9-16.
• 15: Takashi Chikayama , Tetsuro Fujise , Daigo Sekita, A Portable and Efficient Implementation of KL1, Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, p.25-39, September 14-16, 1994
• 16: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 17: GUDEMAN, D. 1993. Representing type information in dynamically typed languages. Tech. Rep. TR93-27, University of Arizona, Department of Computer Science. Sept.
• 18: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 19: HARIDI, S. 1981. Logic programming based on a natural deduction system. Ph.D. thesis, Royal Institute of Technology, Stockholm.
• 20: HARIDI, S. AND FRANZI~N, N. 1999. Tutorial of Oz. Tech. rep. In Mozart documentation, available at http ://www. mozart-oz, org.
• 21: HARIDI, S. AND SAHLIN, D. 1984. Efficient implementation of unification of cyclic structures. Ellis Horwood Limited. In Implementations of Prolog, J. A. Campbell, ed.
• 22: Seif Haridi , Peter Van Roy , Per Brand , Christian Schulte, Programming languages for distributed applications, New Generation Computing, v.16 n.3, p.223-261, 1998 [doi>10.1007/BF03037481]
• 23: Seif Haridi , Peter Van Roy , Gert Smolka, An overview of the design of Distributed Oz, Proceedings of the second international symposium on Parallel symbolic computation, p.176-187, July 20-22, 1997, Maui, Hawaii, United States [doi>10.1145/266670.266726]
• 24: Martin Henz, Objects for concurrent constraint programming, Kluwer Academic Publishers, Norwell, MA, 1998
• 25: HENZ, M. 1997b. Objects in Oz. Ph.D. thesis, Universitgt des Saarlandes, Fachbereich Informatik, Saarbriicken, Germany.
• 26: Robert A. Iannucci, Parallel Machines: Parallel Machine Languages, Kluwer Academic Publishers, Norwell, MA, 1990
• 27: ICHIYOSHI, N., MIYAZAKI, T., AND TAKI, K. 1987. A distributed implementation of Flat GHC on the Multi-PSI. In gth International Conference on Logic Programming. MIT Press, 257-275.
• 28: JAFFAR, J. AND MAHER, M. 1994. Constraint logic programming: A survey. J. Log. Prog. 19/20, 503-581.
• 29: Evelina Lamma , Paola Mello , Cesare Stefanelli , Pascal Van Hentenryck, Improving Distributed Unification through Type Analysis, Proceedings of the Third International Euro-Par Conference on Parallel Processing, p.1181-1190, August 26-29, 1997
• 30: Douglas Lea, Concurrent Programming in Java(TM): Design Principles and Patterns (3rd Edition) (Java (Addison-Wesley)), Addison-Wesley Professional, 2006
• 31: Ho-fung Leung, Distributed Constraint Logic Programming, World Scientific Publishing Co., Inc., River Edge, NJ, 1993
• 32: Ho-fung Leung , Keith L. Clark, Constraint satisfaction in distributed concurrent logic programming, Journal of Symbolic Computation, v.21 n.4-6, p.699-714, April/May/June 1996 [doi>10.1006/jsco.1996.0037]
• 33: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 34: Alberto Martelli , Ugo Montanari, An Efficient Unification Algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.258-282, April 1982 [doi>10.1145/357162.357169]
• 35: MEHL, M. 1999. The Oz virtual machine - records, transients, and deep guards. Ph.D. thesis, Technische FakultSot der UniversitS~t des Saarlandes.
• 36: MEHL, M., SCHULTE, C., AND SMOLKA, G. 1998. Futures and by-need synchronization for Oz.
• 37: K. Mehlhorn , A. Tsakalidis, Data structures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 38: HOZART CONSORTIUM. 1999.The Mozart programming system (Oz 3). Available at http ://www. mozart-oz, org.
• 39: Randy Otte , Paul Patrick , Mark Roy, Understanding CORBA (Common Object Request Broker Architecture), Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 40: David Plainfossé , Marc Shapiro, A Survey of Distributed Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.211-249, September 27-29, 1995
• 41: Andreas Podelski , Gert Smolka, Situated simplification, Theoretical Computer Science, v.173 n.1, p.235-252, Feb. 1997 [doi>10.1016/S0304-3975(96)00197-1]
• 42: J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
• 43: ROKUSAWA, K., NAKASE, A., AND CHIKAYAMA, T. 1996. Distributed memory implementation of KLIC. New Generation Computing 14, 3, 261-280.
• 44: Vijay A. Saraswat, Concurrent constraint programming, MIT Press, Cambridge, MA, 1993
• 45: SCHULTE, C. 1997. Programming constraint inference engines. In Proceedings of the 3rd International Conference on Principles and Practice of Constraint Programming, G. Smolka, Ed. Lecture Notes in Computer Science, vol. 1330. Springer-Verlag, Schlof3 Hagenberg, Austria, 519-533.
• 46: Ehud Shapiro, The family of concurrent logic programming languages, ACM Computing Surveys (CSUR), v.21 n.3, p.413-510, Sep. 1989 [doi>10.1145/72551.72555]
• 47: SMOLKA, G. 1995. The Oz programming model. In Computer Science Today. Lecture Notes in Computer Science, vol. 1000. Springer-Verlag, Berlin, 324-343.
• 48: Gert Smolka, Constraints in OZ, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996 [doi>10.1145/242224.242321]
• 49: Gert Smolka, Concurrent Constraint Programming Based on Functional Programming (Extended Abstract), Proceedings of the 7th European Symposium on Programming: Programming Languages and Systems, p.1-11, March 28-April 04, 1998
• 50: SMOLKA, G., SCHULTE, C., AND VAN ROY, P. 1995. PERDIO--Persistent and distributed programming in Oz. BHBF project proposal. Available at http://www.ps.uni-sb.de.
• 51: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 52: SUN MICROSYSTEMS. 1997. The Remote Method Invocation Specification. Available at http ://www. j avasoft, com.
• 53: SUNDSTROM, A. 1998. Comparative study between Oz 3 and Java. Tech. rep., Uppsala University and Swedish Institute of Computer Science. July.
• 54: TAYLOR, t. 1991. High-performance Prolog implementation. Ph.D. thesis, Basset Department of Computer Science, University of Sydney.
• 55: Gerard Tel, Introduction to distributed algorithms, Cambridge University Press, New York, NY, 1994
• 56: VAN RoY, P. 1994. 1983-1993: The wonder years of sequential Prolog implementation. J. Log. Prog. 19/20, 385-441.
• 57: VAN ROY, P. 1999. On the separation of concerns in distributed programming: Application to distribution structure and fault tolerance in Mozart. In International Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications (PDSIA 99). Tohoku University, Sendal, Japan.
• 58: Peter Van Roy , Per Brand , Seif Haridi , Raphaël Collet, A Lightweight Object Migration Protocol, Workshop on Internet Programming Languages, p.32-46, May 13, 1998
• 59: VAN ROY, P., HARIDI, S., AND BRAND, P. 1999. Distributed progr&mming in Moz&rt - A tutori&l introduction. Tech. rep. In Moz&rt document&tion, &v&il&ble &t http://www.mozart-oz.org.
• 60: Peter Van Roy , Seif Haridi , Per Brand , Gert Smolka , Michael Mehl , Ralf Scheidhauer, Mobile objects in distributed Oz, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.5, p.804-851, Sept. 1997 [doi>10.1145/265943.265972]
• 61: Arthur H. Veen, Dataflow machine architecture, ACM Computing Surveys (CSUR), v.18 n.4, p.365-396, Dec. 1986 [doi>10.1145/27633.28055]
• 62: WARREN, D. H. D. 1977. Applied logic-its use &nd implement&tion &s & progr&mming tool. Ph.D. thesis, University of Edinburgh. Reprinted &s Technic&l Note 290, SRI Intern&tion&l.
• 63: WIKSTROM, C. 1994. Distributed progr&mming in Erl&ng. In the 1st International Symposium on Parallel Symbolic Computation (PASCO 94). World Scientific, Sing&pore, 412-421.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Constraint and logic languages; Concurrent, distributed, and parallel languages; Multiparadigm languages; Data-flow languages
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures; Constraints

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

General Terms:
Algorithms, Languages, Theory

Keywords:
Mozart, Oz, distributed algorithms