A hundred impossibility proofs for distributed computing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A hundred impossibility proofs for distributed computing

Full text

Pdf (3.42 MB)

Source

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

Edmonton, Alberta, Canada

Pages: 1 - 28

Year of Publication: 1989

ISBN:0-89791-326-4

Author

N. Lynch

Lab for Computer Science, MIT, Cambridge, MA

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): 17, Downloads (12 Months): 107, Citation Count: 19

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/72981.72982 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	Karl Abrahamson , Andrew Adler , Lisa Higham , David G. Kirkpatrick, Probabilistic Solitude Detection II: Ring Size Known Exactly, University of British Columbia, Vancouver, BC, Canada, 1987
	2	Hosame Hassan Abu-Amara , Michael C. Loui, Fault-tolerant distributed algorithms for agreement and election, 1988
	3	Yehuda Afek , Eli Gafni, Time and message bounds for election in synchronous and asynchronous complete networks, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.186-195, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323613]
	4	A. V. Aho, J. D. Ullman, A. D. Wyner, and M. Yannakakis. Bounds on the size and transmission rate of communication protocols. Computers and Mathematics wi~h Applications, 8(3):205-214, 1982. This is a later version of{5}.
	5	A. V. Aho, J. D. Unman, and M. Yannakakis. Modeling communication protocols by automata. In Proceedings of the 20th IEEE Symposium on Foundations of Computer Science, pages 267-273, 1979.
	6	James H. Anderson , Mohamed G. Gouda, A New Explanation of the Glitch Phenomenon, University of Texas at Austin, Austin, TX, 1989
	7	Dana Angluin, Local and global properties in networks of processors (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.82-93, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804655]
	8	Eshrat Arjomandi , Michael J. Fischer , Nancy A. Lynch, Efficiency of Synchronous Versus Asynchronous Distributed Systems, Journal of the ACM (JACM), v.30 n.3, p.449-456, July 1983 [doi>10.1145/2402.322387]
	9	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]
	10	It. Attiya, A. Bar-Noy, D. Dolev, D. Koller, D. Peleg, and R. Reischuk. Achievable cases in an asynchronous environment. In Proceedings of 28~h Annual Symposium on Foundations of Compuier Science, pages 337-346, October 1987.
	11	II. Attiya, M. Fischer, D. Wang, and L. Zuck. Reliable communication over an unreliable channel. In progress.
	12	H. Attiya , Y. Mansour, Language complexity on the synchronous anonymous ring, Theoretical Computer Science, v.53 n.2-3, p.169-185, Aug. 1987 [doi>10.1016/0304-3975(87)90062-4]
	13	H. Attiya and M. Snir. Better computing on an anonymous ring. Submitted to publication.
	14	ttagit Attiya, Marc Snir, and Manfred K. Warmuth. Computing on an anonymous ring. October 1988.
	15	B. Awerbuch , O. Goldreich , R. Vainish , D. Peleg, A tradeoff between information and communication in broadcast protocols, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	16	Baruch Awerbuch, Communication-time trade-offs in network synchronization, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.272-276, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323621]
	17	O. Babaoglu, P. Stephenson, and R. Drummond. Reliable broadcasts and communication models: tradeoffs and lower bounds. Dis. tributed Computing, 2:177-189, 1988.
	18	Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.98-108, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41849]
	19	Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
	20	Ofer Biran , Shlomo Moran , Shmuel Zaks, A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.263-275, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62590]
	21	Bard Bloom, Constructing two-writer atomic registers, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.249-259, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41861]
	22	H.L. Bodlaeader. Distributed algorithms, structure and complexity. 198{}. Ph.D. Thesis.
	23	L. Bouge. On the existence of symmetric algorithms to find leaders in networks of communication sequential processes. Rept. No. 86-18, LITP, Univ. Paris 7, Paris(1986). To appear in Acta Informatica.
	24	Michael F. Bridgland , Ronald J. Watro, Fault-tolerant decision making in totally asynchronous distributed systems, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.52-63, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41845]
	25	S. Bums. A formal model for message passing systems. Technical Report TI~-91, Computer Science Dept., Indiana University, May 1980.
	26	James E. Burns , Paul Jackson , Nancy A. Lynch , Michael J. Fischer , Gary L. Peterson, Data Requirements for Implementation of N-Process Mutual Exclusion Using a Single Shared Variable, Journal of the ACM (JACM), v.29 n.1, p.183-205, Jan. 1982 [doi>10.1145/322290.322302]
	27	J. Burns and N. Lynch. Mutual exclusion using indivisible reads and writes. In Proceedings of 18th Annual Allerton Conference on Comma. nica~ions, Control, and Compn~ing, pages 833- 842, 1980. Revision in progress.
	28	K. M. Chandy and J. Misra. On the nonexistence of robust commit protocol. January 1987. Manuscript.
	29	K. M. Chandy , Jayadev Misra, How processes learn, Distributed Computing, v.1 n.1, p.40-52, Jan. 1986 [doi>10.1007/BF01843569]
	30	Benny Chor , Amos Israeli , Ming Li, On processor coordination using asynchronous hardware, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.86-97, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41848]
	31	B A Coan , D Dolev , C Dwork , L Stockmeyer, The distributed firing squad problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.335-345, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22182]
	32	Brian A Coan , Brian M Oki , Elliot K Kolodner, Limitations on database availability when networks partition, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.187-194, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10606]
	33	Brian Coan , Jennifer Lundelius, Transaction commit in a realistic fault model, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.40-51, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10594]
	34	B. A. Coan, Achieving consensus in fault-tolerant distributed computer systems: protocols, lower bounds, and simulations, Massachusetts Institute of Technology, Cambridge, MA, 1987
	35	A.B. Cremers and T.N. ttibbard. An algebraic approach to concurrent programming control and related complexity problenm. Symposium on Algorithms and Complexity, April 1976.
	36	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]
	37	Richard A. DeMillo , Nancy A. Lynch , Michael J. Merritt, Cryptographic protocols, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.383-400, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802214]
	38	E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
	39	D. Dolev. The Byzantine generals strike again. Journal of Algori~llms, 3:14--30, 1982.
	40	D. Dolev and C. Dwork. A study of communication primitives. 1989. Unpublished Manuscript.
	41	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]
	42	Danny Dolev , Ruediger Reischuk, Bounds on information exchange for Byzantine Agreement, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.132-140, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806690]
	43	D. Dolev and H.R. Strong. Authenticated algorithms for Byzantine agreement. SIAM J. Computing, 12(4):656-666, November 1983.
	44	Danny Dolev , Joseph Y Halpern , Raymond H Strong, On the possibility and impossibility of achieving clock synchronization, Journal of Computer and System Sciences, v.32 n.2, p.230-250, April 1986 [doi>10.1016/0022-0000(86)90028-0]
	45	P. Duris and Z. Galil. Two lower bounds in asychronous distributed computation. 28th Annual Symposium on Foundations of Computer Science, 326-330, October 1987.
	46	Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
	47	C Dwork , Y Moses, Knowledge and common knowledge in a Byzantine environment I: crash failures, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.149-169, March 1986, Monterey, California, United States
	48	Cynthia Dwork , Dale Skeen, The inherent cost of nonblocking commitment, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.1-11, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806705]
	49	Cynthia Dwork and Larry Stoekmeyer. Interactive Proof Systems with Finite State Verifiers. Research Report RJ 6262, IBM Almaden Research Center, may 1988.
	50	A D Fekete, Asymptotically optimal algorithms for approximate agreement, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.73-87, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10597]
	51	A. D. Fekete, Asynchronous approximate agreement, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.64-76, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41846]
	52	Paul Feldman and Silvo Micali. Optimal algorithms for Byzantine agreement. May 1988. Paul Feldman Phd thesis.
	53	Michael J. Fischer , Nancy A. Lynch , James E. Burns , Allan Borodin, Distributed FIFO allocation of identical resources using small shared space, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.90-114, Jan. 1989 [doi>10.1145/59287.59292]
	54	Michael J. Fischer , Nancy A. Lynch , Michael Merritt, Easy impossibility proofs for distributed consensus problems, Distributed Computing, v.1 n.1, p.26-39, Jan. 1986 [doi>10.1007/BF01843568]
	55	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]
	56	Michael J. Fischer and Nancy A. Lynch. A lower bound for the time to assure interactive consistency. Information Processing Letters, 14(4):183-186, June 1982.
	57	Michael J. Fischer, Nancy A. Lynch, James E. Burns, and Allan Borodin. Resource allocation with immunity to limited process failure. In Proceedings of the 20ta IEEE Symposium on Foundations of Computer Science, pages 234- 254, October 1979.
	58	Greg N. Frederickson , Nancy A. Lynch, Electing a leader in a synchronous ring, Journal of the ACM (JACM), v.34 n.1, p.98-115, Jan. 1987 [doi>10.1145/7531.7919]
	59	Oded Goldreich , Liuba Shrira, The effects of link failures on computations in asynchronous rings, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.174-185, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10605]
	60	R. L. Graham , A. C. Yao, On the improbability of reaching Byzantine agreements, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.467-478, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73052]
	61	Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
	62	V. Hadzilacos, A knowledge-theoretic analysis of atomic commitment protocols, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.129-134, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28672]
	63	:i. H alpern, N. Megiddo, and A. Munshi. Optimal precision in the presence of uncertainty. Journal of Complexity, 1(2):170-196, December 1985.
	64	Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.50-61, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806735]
	65	Maurice P. Herlihy, Impossibility and universality results for wait-free synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.276-290, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62593]
	66	A. itai and M. Kodeh. Symmetry breaking in distributed networks, in Proceedings of 22"d Annual A CM Symposium on Foundations of Computer Science, pages 150-158, 1981.
	67	R. E. Johnson, Symmetry in distributed systems, Cornell University, Ithaca, NY, 1987
	68	A.R. Karlin and A.C. Yao. Lower bounds to randomized for the Byzantine generals problem. 1984. unpublished.
	69	Richard Koo , Sam Toueg, Effects of message loss on the termination of distributed protocols, Information Processing Letters, v.27 n.4, p.181-188, April 8, 1988 [doi>10.1016/0020-0190(88)90023-3]
	70	E. Korach , S. Moran , S. Zaks, Tight lower and upper bounds for some distributed algorithms for a complete network of processors, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.199-207, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806747]
	71	L. Lamport. On interprocess communication. Distributed Compulin9, 1(1):77-101, 1986.
	72	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]
	73	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]
	74	Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
	75	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]
	76	M. Loui and H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, 4:163-183, 1987.
	77	J. Lundelius and N. Lynch. An upper and lower bound for clock synchronization. Information and Control, 62(2-3):190-204, August/September 1984.
	78	Nancy A. Lynch , Yishay Mansour , Alan Fekete, Data link layer: two impossibility results, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.149-170, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62572]
	79	Nancy A. Lynch , Mark R. Tuttle, Hierarchical correctness proofs for distributed algorithms, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.137-151, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41852]
	80	N.A. Lynch and M. R. Turtle. An introduction to input/output automata. To be published in Centrum voor Wiskunde en Inforrnatica Quarterly. Also in Technical Memo, MIT/LCS/TM- 373, Lab for Computer Science Ma.ssachusettes Institute of Technology, November 1988.
	81	Nancy A. Lynch and Michael J. Fischer. On describing the behavior and implementation of distributed systems. Theoretical Computer Science, 13(1):17-43, January 1981.
	82	Y. Mansour , S. Zaks, On the bit complexity of distributed computations in a ring with a leader, Information and Computation, v.75 n.2, p.162-177, November 1, 1987 [doi>10.1016/0890-5401(87)90056-3]
	83	F. Modugno, M. Merritt, and M.R.. Turtle. Time constrained automata. November 1988. Unpublished manuscript.
	84	Shlomo Moran , Manfred Warmuth, Gap theorems for distributed computing, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.131-150, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10602]
	85	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]
	86	Y. Moses and M. R. Tuttle. Programming; simultaneous actions using common knowledge. Algorithmica, 3(1):121-169, 1988.
	87	Jan K. Pachl , E. Korach , D. Rotem, Lower Bounds for Distributed Maximum-Finding Algorithms, Journal of the ACM (JACM), v.31 n.4, p.905-918, Oct. 1984 [doi>10.1145/1634.1889]
	88	Jan K. Pachl, A lower bound for probabilistic distributed algorithms, Journal of Algorithms, v.8 n.1, p.53-65, March 1987 [doi>10.1016/0196-6774(87)90027-7]
	89	M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
	90	Gary L. Peterson , Michael J. Fischer, Economical solutions for the critical section problem in a distributed system (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.91-97, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803398]
	91	M. Robin. Randomized Byzantine generals. In Proceedings of Z~h Symposium on Foundations of Computer Science, pages 403-409, November 1983.
	92	M. O. Robin. The choice coordination problem. Acta lnforrnatica, 17(2):121-134, 1982.
	93	Rüdiger Reischuk , Meinolf Koshors, Lower Bounds for Synchronous Networks and the Advantage of Local Information, Proceedings of the 2nd International Workshop on Distributed Algorithms, p.374-387, July 08-10, 1987
	94	Nicola Santoro. On the message complexity of Distributed Problems. Technical Report SCS- TR-13, School of Computer Science, Carleton Univerity, Ottawa, Canada, December 1982.
	95	R. Schaffer. On the correctness of atomic multi-writer registers. Bachelor's Thesis, June 1988, Massachusetts Institute Technology. Also, Technical Memo MIT/LCS/TM-364.
	96	A. Segall , O. Wolfson, Transaction commitment at minimal communication cost, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.112-118, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28670]
	97	John Spinelli. Reliable Data Communication in Faulty Networks. Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA, 1988.
	98	G. Taubenfeld, S. Katz, and S. Moran. Impossibility results in the presence of multiple faulty processes. April 1988. Submitted for publication.
	99	Da-Wei Wang , L. D. Zuck, Tight bounds for the sequence transmission problem, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.73-83, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72986]
	100	Jennifer Lundelius Welch, Simulating synchronous processors, Information and Computation, v.74 n.2, p.159-171, Aug. 1987 [doi>10.1016/0890-5401(87)90029-0]
	101	M. Yamashita and T. Kameda. Computing on an Anonymous Network. Technical Report LCCK-T1~-87-15, Simon Fraser University, Burnaby, British Columbia, 1987.
	102	Masafumi Yamashita , Tiko Kameda, Computing on an anonymous network, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.117-130, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62568]
	103	Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]

CITED BY 19

	Alan Fekete , Nancy Lynch , Yishay Mansour , John Spinelli, The impossibility of implementing reliable communication in the face of crashes, Journal of the ACM (JACM), v.40 n.5, p.1087-1107, Nov. 1993
	Danny Hendler , Nir Shavit, Operation-valency and the cost of coordination, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.84-91, July 13-16, 2003, Boston, Massachusetts
	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
	Yves Métivier , Nasser Saheb , Akka Zemmari, Analysis of a randomized rendezvous algorithm, Information and Computation, v.184 n.1, p.109-128, July 10, 2003
	Anish Arora , Mohamed Gouda, Closure and Convergence: A Foundation of Fault-Tolerant Computing, IEEE Transactions on Software Engineering, v.19 n.11, p.1015-1027, November 1993
	Sibsankar Haldar, Constructing regular variables in message passing systems, Journal of Parallel and Distributed Computing, v.65 n.1, p.15-28, January 2005
	Pierre Fraigniaud , David Ilcinkas , Andrzej Pelc, Oracle size: a new measure of difficulty for communication tasks, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Eugene S. Amdur , Samuel M. Weber , Vassos Hadzilacos, On the message complexity of binary byzantine agreement under crash failures, Distributed Computing, v.5 n.4, p.175-186, April 1992
	Paris C. Kanellakis , Alex A. Shvartsman, Efficient parallel algorithms can be made robust, Distributed Computing, v.5 n.4, p.201-217, April 1992
	Philippe Duchon , Nicolas Hanusse , Nasser Saheb , Akka Zemmari, Broadcast in the rendezvous model, Information and Computation, v.204 n.5, p.697-712, May 2006
	David Pritchard , Santosh Vempala, Symmetric network computation, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Benjamin Satzger , Andreas Pietzowski , Wolfgang Trumler , Theo Ungerer, A new adaptive accrual failure detector for dependable distributed systems, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea
	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
	Pierre Fraigniaud , David Ilcinkas , Andrzej Pelc, Tree exploration with advice, Information and Computation, v.206 n.11, p.1276-1287, November, 2008
	Emanuele G. Fusco , Andrzej Pelc, Trade-offs between the size of advice and broadcasting time in trees, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Sibsankar Haldar , K. Vidyasankar, On space-optimality of buffer-based conflict-free constructions of 1-writer 1-reader multivalued atomic variables from safe bits, Journal of Parallel and Distributed Computing, v.69 n.1, p.20-27, January, 2009
	Nuno F. Neves , Miguel Correia , Paulo Verissimo, Solving Vector Consensus with a Wormhole, IEEE Transactions on Parallel and Distributed Systems, v.16 n.12, p.1120-1131, December 2005
	Mansi Ramakrishnan Thoppian , Ravi Prakash, A Distributed Protocol for Dynamic Address Assignment in Mobile Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.5 n.1, p.4-19, January 2006