Reasoning about probabilistic algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Reasoning about probabilistic algorithms

Full text

Pdf (1.63 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the ninth annual ACM symposium on Principles of distributed computing table of contents

Quebec City, Quebec, Canada

Pages: 247 - 264

Year of Publication: 1990

ISBN:0-89791-404-X

Author

Josyula R. Rao

Department of Computer Sciences, The University of Texas at Austin, Austin, Texas

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 15, Citation Count: 3

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/93385.93427 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.

	BGS88	Shaji Bhaskar, Rajive Gupta, and Scott Smolka. Probabilistic algorithms: A survey. Private Communication, 1988.
	CLP84	S. Cohen, Daniel Lehmann, and Arnir Pnueli. Symmetric and economic solution to the mutual exclusion problem in distributed systems. Theoretical Computer Science, 34:215-226, 1984.
	CM88	K. Mani Chandy, Parallel program design: a foundation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
	Dij	Edsger W. Dijkstra. On structures. EWD 928.
	DS90	Edsger W. Dijkstra , Carel S. Scholten, Predicate calculus and program semantics, Springer-Verlag New York, Inc., New York, NY, 1990
	80	Nissim Franeez and M. Rodeh. A distributed data type implemented by a probabilistic communication scheme. In Proceedings of the 21st Symposium on the Foundations of Computer Science, pages 373-379, 1980.
	Her89	Ted Herman. Probabilistic self-stabilization. Private Communication, 1989.
	HS84	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 [doi>10.1145/800057.808660]
	HS85	Sergiu Hart and Micha Sharir. Concurrent probabilistic programs, or: How to schedule if you must. Siam Journal of Computing, 14:991-1012, 1985.
	HSP83	Sergiu Hart , Micha Sharir , Amir Pnueli, Termination of Probabilistic Concurrent Program, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.356-380, July 1983 [doi>10.1145/2166.357214]
	IR81	A. Itai and M. Rodeh. The lord of the ring or probabilistic methods for breaking symmetry in distributive networks. Technical Report RJ 3110, IBM, San :lose, 1981.
	LR81	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]
	LS82	Daniel Lehmann and S. Shelah. Reasoning with time and chance. Information and Control, 53:165-190, 1982.
	Pnu83	Amir Pnueli, On the extremely fair treatment of probabilistic algorithms, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.278-290, December 1983 [doi>10.1145/800061.808757]
	PZ84	Amir Pnueli , Lenore Zuck, Verification of multiprocess probabilistic protocols, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.12-27, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806732]
	PZ86	Amir Pnueli , Lenore Zuck, Verification of multiprocess probabilistic protocols, Distributed Computing, v.1 n.1, p.53-72, Jan. 1986 [doi>10.1007/BF01843570]
	PZ89	Amir Pnueli and Lenore Zuck. Probabilistic verification by tableaux. Private Communication, 1989.
	Rab76	Michael O. Rabin. Algorithms and Complexity, chapter Probabilistic Algorithms, pages 21-40. Academic Press, New York, 1976.
	Rab82a	Michael O. Rabin. The choice coordination problem. Acta Informalica, 17:121- 134, t982.
	Rab82b	Michael O. Rabin. N process synchronization with a 4 log~ n-valued shared variable. J. Comp. Syst. Sciences, 25:66-75, 1982.
	Rao90	Josyula R. Rao, Eventual Determinism: Using Probabilistic Means to Achieve DeterministicEnds, University of Texas at Austin, Austin, TX, 1990
	Var85	Moshe Vardi. Automatic verification of concurrent probabilistic finite state programs. In Proceedings of the ~6th Symposium on the Foundations of Computer Science, pages 327-338, 1985.
	Zuc86	Lenore Zuck. Past Temporal Logic. PhD thesis, The Weizmann institute of Science, 1986.

CITED BY 3

	Nancy Lynch , Isaac Saias , Roberto Segala, Proving time bounds for randomized distributed algorithms, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.314-323, August 14-17, 1994, Los Angeles, California, United States
	Roberto Segala, Verification of randomized distributed algorithms, Lectures on formal methods and performance analysis: first EEF/Euro summer school on trends in computer science, Springer-Verlag New York, Inc., New York, NY, 2002
	Anna Pogosyants , Roberto Segala, Formal verification of timed properties of randomized distributed algorithms, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.174-183, August 20-23, 1995, Ottowa, Ontario, Canada