The decidability of distributed decision tasks (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The decidability of distributed decision tasks (extended abstract)

Full text

Pdf (1.68 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing table of contents

El Paso, Texas, United States

Pages: 589 - 598

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Maurice Herlihy	Computer Science Department Brown University, Providence, RI
Sergio Rajsbaum	Instituto de Matemáticas, U.N.A.M., D.F. 04510, México

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 22, Citation Count: 13

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/258533.258652 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	Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993 [doi>10.1145/153724.153741]
	2	James Aspnes , M. Herlihy, Fast randomized consensus using shared memory, Journal of Algorithms, v.11 n.3, p.441-461, Sep. 1990 [doi>10.1016/0196-6774(90)90021-6]
	3	James Aspnes , Maurice Herlihy , Nir Shavit, Counting networks, Journal of the ACM (JACM), v.41 n.5, p.1020-1048, Sept. 1994 [doi>10.1145/185675.185815]
	4	Hagit Attiya , Amotz Bar-Noy , Danny Dolev , David Peleg , Rüdiger Reischuk, Renaming in an asynchronous environment, Journal of the ACM (JACM), v.37 n.3, p.524-548, July 1990 [doi>10.1145/79147.79158]
	5	H. Attiya and S. Rajsbaum. A combinatorial topology framework for wait-free computability. In Proceedings of the Workshop on Distributed Algorithms and Graphs, 1996.
	6	A. Bas-Noy , D. Dolev, Shared-memory vs. message-passing in an asynchronous distributed environment, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.307-318, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73003]
	7	Ofer Biran , Shlomo Moran , Shumuel Zaks, A combinatorial characterization of the distributed 1-solvable tasks, Journal of Algorithms, v.11 n.3, p.420-440, Sep. 1990 [doi>10.1016/0196-6774(90)90020-F]
	8	Ofer Biran , Shlomo Moran , Shmuel Zaks, Deciding 1-solvability of distributed task is NP-hard (extended abstract), Proceedings of the 16th international workshop on Graph-theoretic concepts in computer science, p.206-220, May 1991, Berlin, Germany
	9	Ofer Biran , Shlomo Moran , Shmuel Zaks, Tight bounds on the round complexity of distributed 1-solvable tasks, Theoretical Computer Science, v.145 n.1-2, p.271-290, July 10, 1995 [doi>10.1016/0304-3975(94)00157-E]
	10	E. Borowsky. Capturing the power of resiliency and set consensus in distributed systems. Technical report, University of California Los Angeles, Los Angeles, California, 1995. and personal communications.
	11	Elizabeth Borowsky , Eli Gafni, Generalized FLP impossibility result for t-resilient asynchronous computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.91-100, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167119]
	12	Soma Chaudhuri, Agreement is harder than consensus: set consensus problems in totally asynchronous systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.311-324, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93431]
	13	Soma Chaudhuri, More choices allow more faults: set consensus problems in totally asynchronous systems, Information and Computation, v.105 n.1, p.132-158, July 1993 [doi>10.1006/inco.1993.1043]
	14	B. Chor and L. Moscovici. Solvability in asynchronous environments. In IEEE Symposium on Foundations of Computer Science (FOCS), 1989.
	15	IBM Corporation , International Business Machines, RISC System/PowerPC System Architecture, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
	16	Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
	17	Danny Dolev , Nancy A. Lynch , Shlomit S. Pinter , Eugene W. Stark , William E. Weihl, Reaching approximate agreement in the presence of faults, Journal of the ACM (JACM), v.33 n.3, p.499-516, July 1986 [doi>10.1145/5925.5931]
	18	Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
	19	E. Gafni and E. Koutsoupias. Three-processor tasks are undecidable, daphne, cs.ucla, edu/eli/undec.ps, 1996.
	20	A. Gottlieb, R. Grishman, C.P. Kruskal, K.P. McAuliffe, L. Rudolph, and M. Snir. The NYU Ultracomputer - designing an MIMD parallel computer. iEEE Transactions on Computers, C-32(2):175-189, February 1984.
	21	Allan Gottlieb , Clyde P. Kruskal, Coordinating parallel processors: a partial unification, ACM SIGARCH Computer Architecture News, v.9 n.6, p.16-24, October 1981 [doi>10.1145/859515.859517]
	22	M. Herlihy and S. Rajsbaum. The decidability of distributed decision tasks. .vw. cs.brown, edu/people- /nph/decide. htal.
	23	Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
	24	Maurice Herlihy , Sergio Rajsbaum, On the decidability of distributed decision tasks, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.279, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248110]
	25	Maurice Herlihy , Sergio Rajsbaum, Set consensus using arbitrary objects (preliminary version), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.324-333, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198119]
	26	Maurice Herlihy , Sergio Rajsbaum, Set consensus using arbitrary objects (preliminary version), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.324-333, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198119]
	27	Maurice Herlihy , Sergio Rajsbaum, Algebraic spans, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.90-99, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224975]
	28	Maurice Herlihy , Nir Shavit, The asynchronous computability theorem for t-resilient tasks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.111-120, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167125]
	29	Maurice Herlihy , Nir Shavit, A simple constructive computability theorem for wait-free computation, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.243-252, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195144]
	30	IBM. System/370 principles of operation. Order Number GA22-7000.
	31	Prasad Jayanti , Sam Toueg, Some Results on the Impossibility, Universality, and Decidability of Consensus, Proceedings of the 6th International Workshop on Distributed Algorithms, p.69-84, November 02-04, 1992
	32	E.H. Jensen, G.W. Hagensen, and J.M. Broughton. A new approach to exclusive data access in shared memory multiprocessors. Technical Report UCRJ.,97663, Lawrence Livermore National Laboratory, November 1987.
	33	C.F. Miller. Decision problems for groups - survey and reflections. In G. Baumslag and C.F. Miller, editors, Algorithms and Classification in Combinatorial Group Theory, volume 23 of Mathematical Sciences Research Institute Publications, pages 1-60. Springer- Verlag, New York, 1989.
	34	S. Moran , Y. Wolfstahl, Extended impossibility results for asynchronous complete networks, Information Processing Letters, v.26 n.3, p.145-151, Nov. 23, 1987 [doi>10.1016/0020-0190(87)90052-4]
	35	J.R. Munkres. Elements Of Algebraic Topology. Addison Wesley, Reading MA, 1984. ISBN 0-201-04586-9.
	36	Michael Saks , Fotios Zaharoglou, Wait-free k-set agreement is impossible: the topology of public knowledge, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.101-110, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167122]
	37	F. Sergeraert. The computability problem in algebraic topology. Advances in Mathematics, 104(1): 1-29, March 1994.
	38	Richard L. Sites, Alpha architecture reference manual, Digital Press, Newton, MA, 1992
	39	E.H. Spanier. Algebraic Topology. Springer-Verlag, New York, 1966.
	40	J. Stillwell. Classical Topology and Combinatorial Group Theory, volume 72 of Graduate Texts in Mathematics. Springer-Ver}ag, New York, 1980.
	41	Gadi Taubenfeld , Shmuel Katz , Shlomo Moran, Initial failures in distributed computations, International Journal of Parallel Programming, v.18 n.4, p.255-276, Aug. 1990 [doi>10.1007/BF01407859]

CITED BY 13

	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal , Matthieu Roy, A hierarchy of conditions for consensus solvability, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.151-160, August 2001, Newport, Rhode Island, United States
	Maurice Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999
	Gunnar Hoest , Nir Shavit, Towards a topological characterization of asynchronous complexity, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.199-208, August 21-24, 1997, Santa Barbara, California, United States
	Eric Ruppert, Determining consensus numbers, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.93-99, August 21-24, 1997, Santa Barbara, California, United States
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Journal of the ACM (JACM), v.50 n.6, p.922-954, November 2003
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	John Havlicek, Computable obstructions to wait-free computability, Distributed Computing, v.13 n.2, p.59-83, April 2000
	Achour Mostéfaoui , Sergio Rajsbaum , Michel Raynal , Matthieu Roy, Condition-based consensus solvability: a hierarchy of conditions and efficient protocols, Distributed Computing, v.17 n.1, p.1-20, February 2004
	Maurice Herlihy , Sergio Rajsbaum, A classification of wait-free loop agreement tasks, Theoretical Computer Science, v.291 n.1, p.55-77, 4 January 2003
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.153-162, July 2001, Hersonissos, Greece
	Xingwu Liu , Zhiwei Xu , Jianzhong Pan, Classifying rendezvous tasks of arbitrary dimension, Theoretical Computer Science, v.410 n.21-23, p.2162-2173, May, 2009
	Eli Gafni, The extended BG-simulation and the characterization of t-resiliency, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Andreas Tielmann, The disagreement power of an adversary: extended abstract, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada