Termination of probabilistic concurrent programs: (extended abstract)

ABSTRACT

The asynchronous execution behavior of several concurrent processes, which may use randomization, is studied. Viewing each process as a discrete Markov chain over the set of common execution states, we give necessary and sufficient conditions for the processes to converge almost surely to a given set of goal states, under any fair, but otherwise arbitrary schedule, provided that the state space is finite. (These conditions can be checked mechanically.) An interesting feature of the proof method is that it depends only on the topology of the transitions and not on the actual values of the probabilities. We also show that in our model synchronization protocols that use randomization are in certain cases no more powerful than deterministic protocols. This is demonstrated by (a) Proving lower bounds on the size of a shared variable necessary to ensure mutual exlusion and lockout-free behavior of the protocol; and (b) Showing that no fully symmetric 'randomized' protocol can ensure mutual exclusion and freedom from lockout.

REFERENCES

• 1: {BFJLP} J. E. Burns, M. J. Fischer, P. Jackson, N. A. Lynch and G. L. Peterson, "Shared Data Requirements for Iplementation of Mutual Exclusion Using a Test-and-set Primitive", Proc. 1978 International Conference on Parallel Processing, 79--87.
• 2: {FR} N. Francez and M. Rodeh, "A Distributed Data Type Implemented by a Probabilistic Communication Scheme", Proc. 21st Symposium on the Foundations of Computer Science (1980), 373--379.
• 3: Daniel J. Lehmann , Amir Pnueli , Jonathan Stavi, Impartiality, Justice and Fairness: The Ethics of Concurrent Termination, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.264-277, July 13-17, 1981
• 4: Daniel Lehmann , Michael O. Rabin, On the advantages of free choice: a symmetric and fully distributed solution to the dining philosophers problem, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-138, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567547]
• 5: {Ra1} M. O. Rabin, "N Process Synchronization by a 4 log N --- Valued Shared Variable", Proc. 21st Symposium on the Foundation of Computer Science (1980), 407--410.
• 6: {Ra2} M. O. Rabin, "The Choice Coordination Problem", Mem. No. UCB/ERL M80/38, Electronics Research Lab. University of California at Berkeley, August 1981.
• 7: John Reif , Paul Spirakis, Distributed algorithms for synchronizing interprocess communication within real time, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.133-145, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802467]
• 8: {IR} A. Itai and M. Rodeh, "The Lord of the Ring, or Probabilistic Methods for Breaking Symmetry in Distributive Networks", Tech. Rep. RJ 3110, IBM, San Jose 1981.