Time-space trade-offs for asynchronous parallel models (Reducibilities and Equivalences)

ABSTRACT

The question of relative efficiencies is studied in the context of a simple model of communicating aynchronous processes. The fundamental problem is whether a simple distributed system, with arbitrary size variables, is any more powerful than a system where only binary valued variables are permitted. The answer was (surprisingly) found to be negative, with an intuitive definition of the power of systems. The development of these notions required formalization of concepts such as equivalence of models, and the reduction of systems between models. It was discovered that requiring a strong definition of equivalence which decreased time apparently results in an increase in space. The trade-offs involved are seen to be tight in one approach to the problem.

REFERENCES

• 1: Gary L. Peterson , Michael J. Fischer, Economical solutions for the critical section problem in a distributed system (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.91-97, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803398]
• 2: Rivest, R. and V. Pratt. The mutual exclusion problem for unreliable processes: preliminary report. Seventeenth Symposium on Foundations of Computer Science (1976), pp. 1-8.
• 3: Leslie Lamport, Concurrent reading and writing, Communications of the ACM, v.20 n.11, p.806-811, Nov. 1977 [doi>10.1145/359863.359878]
• 4: James E. Burns, Mutual exclusion with linear waiting using binary shared variables, ACM SIGACT News, v.10 n.2, Summer 1978 [doi>10.1145/990524.990527]
• 5: R. J. Lipton, Limitations of synchronization primitives with conditional branching and global variables, Proceedings of the sixth annual ACM symposium on Theory of computing, p.230-241, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803900]
• 6: Lipton, R., L. Snyder, and Y. Zalcstein. A comparative study of models of parallel computation. Fifteenth Symposium on Switching and Automata Theory (1974), pp. 145-155.
• 7: Gary Lynn Peterson, The complexity of parallel algorithms, 1979
• 8: Raymond E. Miller , Chee K. Yap, On formulating simultaneity for studying parallelism and synchronization, Proceedings of the tenth annual ACM symposium on Theory of computing, p.105-113, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804338]
• 9: Burns, J., M. Fischer, P. Jackson, N. Lynch, and G. Peterson. Shared data requirements for implementation of mutual exclusion using a test-and-set primitive. Proceedings 1978 International Conference on Parallel Processing.
• 10: Raymond E. Miller , Chee K. Yap, On formulating simultaneity for studying parallelism and synchronization, Proceedings of the tenth annual ACM symposium on Theory of computing, p.105-113, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804338]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Asynchronous/synchronous operation

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Theory