Termination of Probabilistic Concurrent Program

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Termination of Probabilistic Concurrent Program

Full text

Pdf (1.63 MB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 5 , Issue 3 (July 1983) table of contents

Pages: 356 - 380

Year of Publication: 1983

ISSN:0164-0925

Authors

Sergiu Hart	Department of Statistics, Tel Aviv University, Ramat-Aviv, Tel Aviv 69978, Israel
Micha Sharir	Department of Computer Science, School of Mathematical Sciences, Tel Aviv University, Ramat-Aviv, Tel Aviv 69978, Israel
Amir Pnueli	Department of Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 34, Citation Count: 16

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/2166.357214 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BURNS, J.E., FISCHER, M.J., JACKSON, P., LYNCH, N.A., AND PETERSON, G.L. Shared data requirements for implementation of mutual exclusion using a test-and-set primitive. In Proceedings of the 1978 International Conference on Parallel Processing, Aug. 22-25, 1978, pp. 79-87.
	2	DUBINS, L.E., AND SAVAGE, L.J. Inequalities for Stochastic Processes: How to Gamble If You Must. Dover, New York, 1976.
	3	FRANCEZ, N., ANO RODEH, M. A distributed data type implemented by a probabilistic communication scheme. In Proceedings, 21st Symposium on the Foundations of Computer Science, 1980, pp. 373-379.
	4	HART, S., AND SHARIR, M. Concurrent probabilistic programs, or: How to schedule if you must. Tech. Rep., School of Mathematical Sciences, Tel Aviv Univ., Tel Aviv, Israel, May 1982.
	5	Sergiu Hart , Micha Sharir , Amir Pnueli, Termination of probabilistic concurrent programs: (extended abstract), Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-6, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582154]
	6	ITAI, A., AND RODEH, M. The lord of the ring, or probabilistic methods for breaking symmetry in distributive networks. Tech. Rep. RJ 3110, IBM Corp., San Jose, Calif., 1981.
	7	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
	8	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]
	9	RABIN, M.O. N process synchronization by a (4 log N)-valued shared variable. In Proceedings, 21st Symposium on the Foundations of Computer Science, 1980, pp. 407-410.
	10	RABIN, M.O. The choice coordination problem. Acta Inf. 17 (1982), 121-134.
	11	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]
	12	Micha Sharir , Amir Pnueli , Sergiu Harts, Verification of probabilistic programs, SIAM Journal on Computing, v.13 n.2, p.292-314, May 1984 [doi>10.1137/0213021]

CITED BY 16

	Costas Courcoubetis , Mihalis Yannakakis, The complexity of probabilistic verification, Journal of the ACM (JACM), v.42 n.4, p.857-907, July 1995
	Carroll Morgan , Annabelle McIver , Karen Seidel, Probabilistic predicate transformers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.3, p.325-353, May 1996
	Annabelle McIver , Carroll Morgan, Almost-certain eventualities and abstract probabilities in the quantitative temporal logic qTL, Theoretical Computer Science, v.293 n.3, p.507-534, 9 February 2003
	Isaac Saias, Proving probabilistic correctness statements: the case of Rabin's algorithm for mutual exclusion, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.263-274, August 10-12, 1992, Vancouver, British Columbia, Canada
	Annabelle McIver , Carroll Morgan, An elementary proof that Herman's ring is Θ(N²), Information Processing Letters, v.94 n.2, p.79-84, 30 April 2005
	Josyula R. Rao, Reasoning about probabilistic parallel programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.798-842, May 1994
	Josyula R. Rao, Reasoning about probabilistic algorithms, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.247-264, August 22-24, 1990, Quebec City, Quebec, Canada
	Sergiu Hart , Micha Sharir(, Probabilistic temporal logics for finite and bounded models, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.1-13, December 1984
	Christel Baier , Marta Kwiatkowska, Model checking for a probabilistic branching time logic with fairness, Distributed Computing, v.11 n.3, p.125-155, August 1998
	Anna Pogosyants , Roberto Segala , Nancy Lynch, Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study, Distributed Computing, v.13 n.3, p.155-186, July 2000
	Annabelle McIver , Carroll Morgan, Abstraction and refinement in probabilistic systems, ACM SIGMETRICS Performance Evaluation Review, v.32 n.4, p.41-47, March 2005
	Isabelle Gnaedig, Induction for positive almost sure termination, Proceedings of the 9th ACM SIGPLAN international symposium on Principles and practice of declarative programming, July 14-16, 2007, Wroclaw, Poland
	François Laroussinie , Jeremy Sproston, State explosion in almost-sure probabilistic reachability, Information Processing Letters, v.102 n.6, p.236-241, June, 2007
	Luca de Alfaro , Thomas A. Henzinger , Orna Kupferman, Concurrent reachability games, Theoretical Computer Science, v.386 n.3, p.188-217, November, 2007
	Józef Winkowski, An Algebraic Framework for Defining Random Concurrent Behaviours, Fundamenta Informaticae, v.85 n.1-4, p.481-496, September 2008
	Marta Kwiatkowska , Gethin Norman , Jeremy Sproston , Fuzhi Wang, Symbolic model checking for probabilistic timed automata, Information and Computation, v.205 n.7, p.1027-1077, July, 2007