Spreading rumors rapidly despite an adversary

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Spreading rumors rapidly despite an adversary

Full text

Pdf (880 KB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 143 - 151

Year of Publication: 1996

ISBN:0-89791-800-2

Authors

James Aspnes	Yale University, Department of Computer Science, 51 Prospect, Street/P.O. Box 208285, New Haven, CT
William Hurwood	Yale University, Department of Mathematics, P.O. Box 208283, New Haven CT

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 10, Citation Count: 4

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/248052.248077 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, On achieving consensus using a shared memory, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.291-302, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62594]
	2	Yehuda Afek , Danny Dolev , Hagit Attiya , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.1-13, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93394]
	3	M. Ajtaj, J. Aspnes, C. Dwork, and O. Waarts. A theory of competitive analysis for distributed algorithms. In Proc. 33rd IEEE Symposium on Foundations of Computer Science, pp. 401-411, November 1994. Full version available.
	4	James Anderson, Composite registers, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.15-29, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93396]
	5	Richard J. Anderson , Heather Woll, Wait-free parallel algorithms for the union-find problem, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.370-380, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103458]
	6	James Aspnes, Time- and space-efficient randomized consensus, Journal of Algorithms, v.14 n.3, p.414-431, May 1993 [doi>10.1006/jagm.1993.1022]
	7	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]
	8	J. Aspnes , M. Herlihy, Wait-free data structures in the asynchronous PRAM model, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.340-349, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97701]
	9	J. Aspnes and O. Waarts. Randomized consensus in expected O(n log2 n) operations per processor. In Proc 3$rd IEEE Symposium on Foundations of Compute~ Science, pp. 137-146, October 1992.
	10	James Aspnes , Orli Waarts, Modular competitiveness for distributed algorithms, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.237-246, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237869]
	11	Yonatan Aumann , Michael A. Bender, Efficient Asynchronous Consensus with the Value-Oblivious Adversary Scheduler, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.622-633, July 08-12, 1996
	12	Hagit Attiya , Maurice Herlihy , Ophir Rachman, Efficient Atomic Snapshots Using Lattice Agreement (Extended Abstract), Proceedings of the 6th International Workshop on Distributed Algorithms, p.35-53, November 02-04, 1992
	13	Hagit Attiya , Ophir Rachman, Atomic snapshots in O(n log n) operations, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.29-40, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164055]
	14	S. Ben-David , A. Borodin , R. Karp , G. Tardos , A. Wigderson, On the power of randomization in online algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.379-386, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100268]
	15	Elizabeth Borowsky , Eli Gafni, Immediate atomic snapshots and fast renaming, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.41-51, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164056]
	16	Gabriel Bracha , Ophir Rachman, Randomized Consensus in Expected O(n²log n) Operations, Proceedings of the 5th International Workshop on Distributed Algorithms, p.143-150, October 07-09, 1991
	17	T. Chandra and C. Dwork. Using consensus to solve atomic snapshots. Submitted for Publication
	18	Tushar Deepak Chandra, Polylog randomized wait-free consensus, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.166-175, May 23-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/248052.248083]
	19	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]
	20	D. Dolev , N. Shavit, Bounded concurrrent time-stamp systems are constructible, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.454-466, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73051]
	21	Cynthia Dwork , Serge A. Plotkin , Maurice Herlihy , Orli Waarts, Time-lapse snapshots, Symposium proceedings on Theory of computing and systems, p.154-170, June 1992, Haifa, Israel
	22	Cynthia Dwork , Maurice Herlihy, Bounded round number, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.53-64, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164058]
	23	Cynthia Dwork , Orli Waarts, Simple and efficient bounded concurrent timestamping or bounded concurrent timestamp systems are comprehensible!, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.655-666, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129776]
	24	S. Even , B. Monien, On the number of rounds necessary to disseminate information, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.318-327, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72969]
	25	Rainer Gawlick , Nancy Lynch , Nir Shavit, Concurrent timestamping made simple, Symposium proceedings on Theory of computing and systems, p.171-183, June 1992, Haifa, Israel
	26	S. Haldar. Efficient bou~tded timestamping using traceable use abstraction - Is writer's guessing better than reader's telling? Technical Report RUU-CS-93-28, Department of Computer Science, Utrecht, September 1993.
	27	Maurice Herlihy, Randomized wait-free concurrent objects (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.11-21, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112602]
	28	A. Israeli and M. Li. Bounded time stamps. In Proc. ~Sth iEEE Symposium on Foundations of Computer Science, 1987.
	29	A. Israeli and M. Pinhasov. A concurrent time-stamp scheme which is linear in time and space. Manuscript, 1991.
	30	Lefteris M. Kirousis , Paul G. Spirakis , Philippas Tsigas, Reading Many Variables in One Atomic Operation: Solutions With Linear or Sublinear Complexity, Proceedings of the 5th International Workshop on Distributed Algorithms, p.229-241, October 07-09, 1991
	31	Y. Riany, N. Shavit and D. Touitou. Practical Snapshots. In Proceedings of israel Symposium on Theory of Computing and Systems, 1994.
	32	Michael Saks , Nir Shavit , Heather Woll, Optimal time randomized consensus—making resilient algorithms fast in practice, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.351-362, January 28-30, 1991, San Francisco, California, United States
	33	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
	34	P. M. B. Vitanyi and B. Awerbuch. Atomic shared register access by asynchronous hardware. In Proc. ~Tth IEEE Symposium on Foundations of Computer Science, 1986.

CITED BY 4

	Yonatan Aumann, Efficient asynchronous consensus with the weak adversary scheduler, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.209-218, August 21-24, 1997, Santa Barbara, California, United States
	Yonatan Aumann , Avivit Kapah-Levy, Cooperative sharing and asynchronous consensus using single-reader single-writer registers, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.61-70, January 17-19, 1999, Baltimore, Maryland, United States
	Tassos Dimitriou , Sotiris Nikoletseas , Paul Spirakis, The infection time of graphs, Discrete Applied Mathematics, v.154 n.18, p.2577-2589, 1 December 2006
	Cynthia Dwork, Distributed computing column, ACM SIGACT News, v.27 n.3, p.50-54, Sept. 1996