Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The defining characteristic of a distributed system is the (temporal) distance between components; communication time is non-trivial compared to processing time. Because of this, the design of efficient distributed computations involves trade-offs between maximizing the amount of parallelism and minimizing communication costs. We argue that any sort of centralized control, whether in user-level algorithms or at the systems level, impairs efficiency. We then introduce a scheme for automatic process synchronization that meets our locality criterion.

REFERENCES

• Agh: Gul Agha, Actors: a model of concurrent computation in distributed systems, MIT Press, Cambridge, MA, 1986
• CaH: Roy H. Campbell , A. Nico Habermann, The specification of process synchronization by path expressions, Operating Systems, Proceedings of an International Symposium, p.89-102, April 23-25, 1974
• ChM: K. M. Chandy , J. Misra, Asynchronous distributed simulation via a sequence of parallel computations, Communications of the ACM, v.24 n.4, p.198-206, April 1981 [doi>10.1145/358598.358613]
• Cli: William D Clinger, Foundations of Actor Semantics, Massachusetts Institute of Technology, Cambridge, MA, 1981
• Fel: Jerome A. Feldman, High level programming for distributed computing, Communications of the ACM, v.22 n.6, p.353-368, June 1979 [doi>10.1145/359114.359127]
• GCS: D Garnick, AT Cohen, and H Sowizral, Timestamping in Virtual Time Systems, to appear in Proceedings of IFIP Conference on Temporal Aspects in Information Systems, North- Holland 1988.
• Gel: David Gelernter, Generative communication in Linda, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.80-112, Jan. 1985 [doi>10.1145/2363.2433]
• HeB: C Hewitt and H Baker, Laws for Communicating Parallel Processes, 1977 IFIP Congress Proceedings, North-Holland, 1977.
• Jef: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• JeS: D Jefferson and H Sowizral, Fast Concurrent Simulation using the Time Warp Mechanism - Part 1: Local Control, Rand, 1983.
• Lam78: 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]
• Lam80: Leslie Lamport, "Sometime" is sometimes "not never": on the temporal logic of programs, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.174-185, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567463]
• Lis: B Liskov, Overview of the Argus Language and Syztem, MIT Lab for Computer Science, Programming Methodology Group Memo 40, 1984.
• LCJS: B. Liskov , D. Curtis , P. Johnson , R. Scheifer, Implementation of Argus, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.111-122, November 08-11, 1987, Austin, Texas, United States [doi>10.1145/41457.37514]
• LHG: B Liskov, M Herlihy, and L Gilbert, Limitations of Synchronous Communication with Static Process Structure in Languages for Distributed Computing, MIT Lab for Computer Science, Programming Methodology Grp Memo 41-1, Oct 1985.
• Ree78: D. P. Reed, NAMING AND SYNCHRONIZATION IN A DECENTRALIZED COMPUTER SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1978
• Ree83: David P. Reed, Implementing atomic actions on decentralized data, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.3-23, Feb. 1983 [doi>10.1145/357353.357355]
• Tan: Andrew S. Tanenbaum, Computer Networks, Prentice Hall PTR, Upper Saddle River, NJ, 1985

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

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

General Terms:
Design, Performance, Theory