The distributed firing squad problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The distributed firing squad problem

Full text

Pdf (1.09 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the seventeenth annual ACM symposium on Theory of computing table of contents

Providence, Rhode Island, United States

Pages: 335 - 345

Year of Publication: 1985

ISBN:0-89791-151-2

Authors

B A Coan	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
D Dolev	Computer Science Department, Hebrew University, Jerusalem, Israel
C Dwork	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
L Stockmeyer	Computer Science Department, IBM Research Laboratory, San Jose, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 20, Citation Count: 7

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

	ADG	Chagit Attiya , Danny Dolev , Joseph Gil, Asynchronous Byzantine consensus, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.119-133, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806740]
	BD	Broder, A., and Dolev, D., Flipping coins in many pockets (Byzantine agreement on uniformly random values), Proc. 25th Syrup. on Foundations of Computer Science, 1984, pp. 157-170.
	BL	Burns, j. E., and Lynch, N. A., The Byzantine firing squad problem, manuscript, submitted for publication,
	DDS	Dolev, D., Dwork, C., and Stockmeyer, L., On the minimal synchronism needed for distributed consensus, Proc. 2 4th Syrup. on Foundations of Computer Science, 1983, pp. 393-402.
	DFFLS	Dolev, D., Fischer, M.J., Fowler, R., Lynch, N.A., and Strong, H.R., Efficient Byzantine agreement without authentication, Information and Control 52 (1982), pp. 257- 274,
	DHS	Danny Dolev , Joe Halpern , H. Raymond Strong, On the possibility and impossibility of achieving clock synchronization, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.504-511, December 1984 [doi>10.1145/800057.808720]
	DLS	Dwork, C., Lynch, N., and Stockmeyer, L., Consensus in the presence of partial synchrony, Proc. 3rd ACbt Syrup. on Principles of Distributed Computing, 1984, pp. 103- i 18.
	DRS	Dolev, D., Reischuk, R., and Strong, H. R., Eventual is earlier than immediate, Proc. 23rd Syrup. on Foundations of Computer Science, 1982, pp. 196-203.
	DS	Dolev, D. and Strong, H. R., Authenticated algorithms for Byzantine agreement, SiAM J. Computing 12 (1983), pp. 656-666.
	FLM	Fischer, M. J., Lynch, N. A., and Merritt, M., Shifting scenarios: easy impossibility proofs for distributed consensus problems, manuscript.
	FLP	Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588060]
	HSSD	Joseph Y. Halpern , Barbara Simons , Ray Strong , Danny Dolev, Fault-tolerant clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.89-102, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806739]
	L	L. Lamport, The Weak Byzantine Generals Problem, Journal of the ACM (JACM), v.30 n.3, p.668-676, July 1983 [doi>10.1145/2402.322398]
	LF	Lamport, L., and Fischer, M.J., Byzantine generals and transaction commit protocols, manuscript.
	LL	Jennifer Lundelius , Nancy Lynch, A new fault-tolerant algorithm for clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.75-88, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806738]
	LM	Leslie Lamport , P. M. Melliar-Smith, Byzantine clock synchronization, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.68-74, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806737]
	LSP	Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
	Mo	Moore, E. F., The firing squad synchronization problem, in: E. F. Moore, Ed., Sequential Machines, Selected Papers, Addison-Wesley, Reading, MA, 1964.
	Me	Merritt, M., personal communication.

CITED BY 7

	N. Lynch, A hundred impossibility proofs for distributed computing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.1-28, June 1989, Edmonton, Alberta, Canada
	Michael Barborak , Anton Dahbura , Minoslaw Malek, The consensus problem in fault-tolerant computing, ACM Computing Surveys (CSUR), v.25 n.2, p.171-220, June 1993
	M. Herlihy , Mark R. Tuttle, Lower bounds for wait-free computation in message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.347-362, August 22-24, 1990, Quebec City, Quebec, Canada
	J Y Halpern , N Megiddo , A A Munshi, Optimal precision in the presence of uncertainty, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.346-355, May 06-08, 1985, Providence, Rhode Island, United States
	Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.59-70, August 1985, Minaki, Ontario, Canada
	Brian A Coan, A communication-efficient canonical form for fault-tolerant distributed protocols, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.63-72, August 11-13, 1986, Calgary, Alberta, Canada
	Ariel Daliot , Danny Dolev, Self-stabilizing byzantine agreement, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA