A shared resource algorithm for distributed simulation

ABSTRACT

We propose a distributed simulation method which is particularly well suited for the simulation of large synchronous networks. In general, distributed simulation has significant potential for alleviating the time and memory constraints often encountered when using conventional simulation techniques. Currently proposed methods for distributed simulation suffer performance degradation due to the employment of strategies for preventing deadlock and due to artificial blocking of processes. We describe a new method for doing distributed simulation which is deadlock free whenever the physical system being simulated is deadlock free. Furthermore, our method does not suffer from artificial blocking of processes.

REFERENCES

• 1: R. E. Bryant, SIMULATION OF PACKET COMMUNICATION ARCHITECTURE COMPUTER SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 2: K. M Chandy , Jayadev Misra, An Axiomatic Proof Technique for Networks of Communicating Processes, University of Texas at Austin, Austin, TX, 1979
• 3: Chandy, K.M. and Misra, J. "Distributed Simulation: A Case Study in Design and Verification of Distributed Programs", IEEE Trans on Software Engineering, SE-5, 5, Sept 1979, 440-452.
• 4: Chandy, K.M. and Misra, J. "Deadlock Absence Proofs for Networks of Communicating Processes", Information Processing Letters, 9, 4, Nov 1979, 185-189.
• 5: 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]
• 6: Dennis, J.B. "First Version of a Data Flow Procedure Language", MAC Tech Memo 61, MIT, Cambridge Mass., Nov 1973.
• 7: A. Nico Habermann, Synchronization of communicating processes, Communications of the ACM, v.15 n.3, p.171-176, March 1972 [doi>10.1145/361268.361277]
• 8: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 9: 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]
• 10: Owicki, S.S. and Gries, D. "An Axiomatic Proof Technique for Parallel Programs", Acta Informatica, 6, 3, 1976, 319-340.
• 11: Peacock, J.K., Manning, E. and Wong, J.W. "Synchronization of Distributed Simulation Using Broadcast Algorithms", Computer Networks, North Holland Publishing Co., 4, 1980, 3-10.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Distributed

General Terms:
Algorithms, Design