Complexity of network synchronization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Complexity of network synchronization

Full text

Pdf (1.62 MB)

Source

Journal of the ACM (JACM) archive
Volume 32 , Issue 4 (October 1985) table of contents

Pages: 804 - 823

Year of Publication: 1985

ISSN:0004-5411

Author

Baruch Awerbuch

Massachusetts Institute of Technology, Cambridge

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 140, Citation Count: 106

Additional Information:

abstract references cited by index terms review 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/4221.4227 What is a DOI?

ABSTRACT

The problem of simulating a synchronous network by an asynchronous network is investigated. A new simulation technique, referred to as a synchronizer, which is a new, simple methodology for designing efficient distributed algorithms in asynchronous networks, is proposed. The synchronizer exhibits a trade-off between its communication and time complexities, which is proved to be within a constant factor of the lower bound.

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	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]
	2	AWERBUCH, B.Applications of the network synchronization for distributed BFS and Max-Flow algorithms. Preprint. To appear in Networks.
	3	BOLLOBAS, B.Extremal Graph Theory. Academic Press, New York, 1978.
	4	Denise Marie Eckstein, Parallel graph processing using depth-first search and breadth-first search., 1977
	5	Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
	6	GALLAGER, R. G. Distributed minimum hop algorithms. Tech. Rep. LIDS-P-! I75, M.I.T., Cambridge, Mass., Jan. 1982.
	7	R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
	8	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]
	9	Fred B. Schneider, Synchronization in Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.125-148, April 1982 [doi>10.1145/357162.357163]
	10	SEGALL, A.Decentralized maximum flow algorithms. Networks 12 (1982), 213-230.
	11	SEGALL, A.Distributed network protocols. IEEE Trans. Inf. Theory IT-29, 1 (Jan. 1983), 23-25.
	12	Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]

CITED BY 106

	Shing-Tsaan Huang , Tzong-Jye Liu , Su-Shen Hung, Asynchronous Phase Synchronization in Uniform Unidirectional Rings, IEEE Transactions on Parallel and Distributed Systems, v.15 n.4, p.378-384, April 2004
	B. Awerbuch, Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.230-240, January 1987, New York, New York, United States
	Yehuda Afek , Baruch Awerbuch , Serge Plotkin , Michael Saks, Local management of a global resource in a communication network, Journal of the ACM (JACM), v.43 n.1, p.1-19, Jan. 1996
	Benny Chor , Michael Merritt , David B. Shmoys, Simple constant-time consensus protocols in realistic failure models, Journal of the ACM (JACM), v.36 n.3, p.591-614, July 1989
	David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989
	Baruch Awerbuch , David Peleg, Online tracking of mobile users, Journal of the ACM (JACM), v.42 n.5, p.1021-1058, Sept. 1995
	Aomar Maddi , Fodil Dahamni, An efficient algorithm for causal messages ordering, Proceedings of the 2001 ACM symposium on Applied computing, p.499-503, March 2001, Las Vegas, Nevada, United States
	S. Even , S. Rajsbaum, The use of a synchronizer yields maximum computation rate in distributed networks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.95-105, May 13-17, 1990, Baltimore, Maryland, United States
	Michael Elkin, Computing almost shortest paths, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.53-62, August 2001, Newport, Rhode Island, United States
	Barun Chandra , Gautam Das , Giri Narasimhan , José Soares, New sparseness results on graph spanners, Proceedings of the eighth annual symposium on Computational geometry, p.192-201, June 10-12, 1992, Berlin, Germany
	Shlomi Dolev , Evangelos Kranakis , Danny Krizanc , David Peleg, Bubbles: adaptive routing scheme for high-speed dynamic networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.528-537, May 29-June 01, 1995, Las Vegas, Nevada, United States
	S. Rajsbaum , M. Sidi, On the Performance of Synchronized Programs in Distributed Networks with Random Processing Times and Transmission Delays, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.939-950, September 1994
	I A Cimet , P R Srikanta Kumar, A resilient distributed protocol for network synchronization, ACM SIGCOMM Computer Communication Review, v.16 n.3, p.358-367, Aug. 5, 1986
	Yehuda Afek , Gad M. Landau , Baruch Schieber , Moti Yung, The power of multimedia: combining point-to point and multi-access networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.90-104, August 15-17, 1988, Toronto, Ontario, Canada
	Michael Ben-Or , Ran Canetti , Oded Goldreich, Asynchronous secure computation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.52-61, May 16-18, 1993, San Diego, California, United States
	Alessandro Panconesi , Aravind Srinivasan, Improved distributed algorithms for coloring and network decomposition problems, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.581-592, May 04-06, 1992, Victoria, British Columbia, Canada
	Jennifer L. Welch , Leslie Lamport , Nancy Lynch, A lattice-structured proof of a minimum spanning, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.28-43, August 15-17, 1988, Toronto, Ontario, Canada
	Baruch Awerbuch , Alan Baratz , David Peleg, Cost-sensitive analysis of communication protocols, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.177-187, August 22-24, 1990, Quebec City, Quebec, Canada
	Nathan Linial , Michael Saks, Decomposing graphs into regions of small diameter, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.320-330, January 28-30, 1991, San Francisco, California, United States
	B. Awerbuch, Shortest paths and loop-free routing in dynamic networks, ACM SIGCOMM Computer Communication Review, v.20 n.4, p.177-187, Sep. 1990
	A. Goldberg , S. Plotkin , G. Shannon, Parallel symmetry-breaking in sparse graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.315-324, January 1987, New York, New York, United States
	B. Awerbuch, Randomized distributed shortest paths algorithms, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.490-500, May 14-17, 1989, Seattle, Washington, United States
	Yehuda Afek , Eli Gafni , Adi Rosén, The slide mechanism with applications in dynamic networks, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.35-46, August 10-12, 1992, Vancouver, British Columbia, Canada
	Gil Neiger , Sam Toueg, Substituting for real time and common knowledge in asynchronous distributed systems, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.281-293, August 10-12, 1987, Vancouver, British Columbia, Canada
	Baruch Awerbuch , Lenore J. Cowen , Mark A. Smith, Efficient asynchronous distributed symmetry breaking, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.214-223, May 23-25, 1994, Montreal, Quebec, Canada
	Baruch Awerbuch , Lenore J. Cowen , Mark A. Smith, Efficient asynchronous distributed symmetry breaking, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.214-223, May 23-25, 1994, Montreal, Quebec, Canada
	Baruch Awerbuch , Shay Kutten , Yishay Mansour , Boaz Patt-Shamir , George Varghese, Time optimal self-stabilizing synchronization, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.652-661, May 16-18, 1993, San Diego, California, United States
	Yoram Moses , Sergio Rajsbaum, The unified structure of consensus: a layered analysis approach, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.123-132, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Shay Kutten , David Peleg, Fast distributed construction of k-dominating sets and applications, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.238-251, August 20-23, 1995, Ottowa, Ontario, Canada
	Menelaos I. Karavelas , Leonidas J. Guibas, Static and kinetic geometric spanners with applications, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.168-176, January 07-09, 2001, Washington, D.C., United States
	Paul F. Reynolds, Jr. , Craig Williams , Raymond R. Wagner, Jr., Isotach Networks, IEEE Transactions on Parallel and Distributed Systems, v.8 n.4, p.337-348, April 1997
	Alessandro Panconesi , Aravind Srinivasan, Fast randomized algorithms for distributed edge coloring, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.251-262, August 10-12, 1992, Vancouver, British Columbia, Canada
	Maurice Herlihy , Sergio Rajsbaum , Mark R. Tuttle, Unifying synchronous and asynchronous message-passing models, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.133-142, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Eli Gafni, Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.143-152, June 28-July 02, 1998, Puerto Vallarta, Mexico
	A. Goldberg , R. Tarjan, Solving minimum-cost flow problems by successive approximation, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.7-18, January 1987, New York, New York, United States
	Marc Bui , Franck Butelle , Christian Lavault, A distributed algorithm for constructing a minimum diameter spanning tree, Journal of Parallel and Distributed Computing, v.64 n.5, p.571-577, May 2004
	David Peleg , Jeffrey D. Ullman, An optimal synchronizer for the hypercube, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.77-85, August 10-12, 1987, Vancouver, British Columbia, Canada
	J.-M. Hélary , M. Hurfin , A. Mostefaoui , M. Raynal , F. Tronel, Computing Global Functions in Asynchronous Distributed Systems with Perfect Failure Detectors, IEEE Transactions on Parallel and Distributed Systems, v.11 n.9, p.897-909, September 2000
	Valmir C. Barbosa , Eli Gafni, Concurrency in heavily loaded neighborhood-constrained systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.562-584, Oct. 1989
	Edith Cohen , Uri Zwick, All-pairs small-stretch paths, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.93-102, January 05-07, 1997, New Orleans, Louisiana, United States
	Sukumar Ghosh , Arobinda Gupta , Ted Herman , Sriram V. Pemmaraju, Fault-containing self-stabilizing algorithms, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.45-54, May 23-26, 1996, Philadelphia, Pennsylvania, United States
	Lujun Jia , Rajmohan Rajaraman , Torsten Suel, An efficient distributed algorithm for constructing small dominating sets, Distributed Computing, v.15 n.4, p.193-205, December 2002
	Ted Herman, Phase Clocks for Transient Fault Repair, IEEE Transactions on Parallel and Distributed Systems, v.11 n.10, p.1048-1057, October 2000
	Baruch Awerbuch , Boaz Patt-Shamir , David Peleg , Michael Saks, Adapting to asynchronous dynamic networks (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.557-570, May 04-06, 1992, Victoria, British Columbia, Canada
	Baruch Awerbuch , David Peleg, Concurrent online tracking of mobile users, ACM SIGCOMM Computer Communication Review, v.21 n.4, p.221-233, Sept. 1991
	Gerard Tel , Ephraim Korach , Shmuel Zaks, Synchronizing ABD networks, IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.66-69, Feb. 1994
	Naoshi Sakamoto, Comparison of initial conditions for distributed algorithms on anonymous networks, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.173-179, May 04-06, 1999, Atlanta, Georgia, United States
	Michal Parnas , Dana Ron, Testing the diameter of graphs, Random Structures & Algorithms, v.20 n.2, p.165-183, March 2002
	Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988
	Shlomi Dolev , Amos Israeli , Shlomo Moran, Uniform Dynamic Self-Stabilizing Leader Election, IEEE Transactions on Parallel and Distributed Systems, v.8 n.4, p.424-440, April 1997
	Stefan Dobrev , Peter Ružička, On the communication complexity of strong time-optimal distributed algorithms, Nordic Journal of Computing, v.5 n.2, p.87-104, Summer 1998
	Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA
	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003
	Michael Elkin, A faster distributed protocol for constructing a minimum spanning tree, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Baruch Awerbuch , Oded Goldreich , Ronen Vainish , David Peleg, A trade-off between information and communication in broadcast protocols, Journal of the ACM (JACM), v.37 n.2, p.238-256, April 1990
	B. Schieber, Calling names in nameless networks, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.319-328, June 1989, Edmonton, Alberta, Canada
	David Peleg , Eli Upfal, A tradeoff between space and efficiency for routing tables, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.43-52, May 02-04, 1988, Chicago, Illinois, United States
	Lenore J. Cowen, Compact routing with minimum stretch, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.255-260, January 17-19, 1999, Baltimore, Maryland, United States
	Carol Critchlow , Kim Taylor, The inhibition spectrum and the achievement of causal consistency, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.31-42, August 22-24, 1990, Quebec City, Quebec, Canada
	John N. Tsitsiklis , George D. Stamoulis, On the average communication complexity of asynchronous distributed algorithms, Journal of the ACM (JACM), v.42 n.2, p.382-400, March 1995
	Carol Critchlow , Kim Taylor, The inhibition spectrum and the achievement of causal consistency, Distributed Computing, v.10 n.1, p.11-27, July 1996
	Bogdan S. Chlebus , Dariusz R. Kowalski, A better wake-up in radio networks, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Christian Boulinier , Franck Petit , Vincent Villain, When graph theory helps self-stabilization, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
	Michel Raynal , Mukesh Singhal, Logical Time: Capturing Causality in Distributed Systems, Computer, v.29 n.2, p.49-56, February 1996
	Sukumar Ghosh , Arobinda Gupta , Sriram V. Pemmaraju, A self-stabilizing algorithm for the maximum flow problem, Distributed Computing, v.10 n.4, p.167-180, July 1997
	Thomas Moscibroda , Roger Wattenhofer, Facility location: distributed approximation, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Ariel Orda , Raphael Rom, Distributed shortest-path protocols for time-dependent networks, Distributed Computing, v.10 n.1, p.49-62, July 1996
	Swati Sinha Deb , M. E. Woodward, A new distributed QoS routing algorithm based on Fano's method, Computer Networks and ISDN Systems, v.48 n.2, p.155-174, 6 June 205
	Fabian Kuhn , Tim Nieberg , Thomas Moscibroda , Roger Wattenhofer, Local approximation schemes for ad hoc and sensor networks, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany
	Guanghui He , Rong Zheng , Indranil Gupta , Lui Sha, A framework for time indexing in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.1 n.1, p.101-133, August 2005
	Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, On the locality of bounded growth, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Zvi Lotker , Elan Pavlov , Boaz Patt-Shamir , David Peleg, MST construction in O(log log n) communication rounds, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Michael Elkin, Computing almost shortest paths, ACM Transactions on Algorithms (TALG), v.1 n.2, p.283-323, October 2005
	V. C. Barbosa, Strategies for the Prevention of Communication Deadlocks in Distributed Parallel Programs, IEEE Transactions on Software Engineering, v.16 n.11, p.1311-1316, November 1990
	K. B. Lakshmanan , K. Thulasiraman , M. A. Comeau, An Efficient Distributed Protocol for Finding Shortest Paths in Networks with Negative Weights, IEEE Transactions on Software Engineering, v.15 n.5, p.639-644, May 1989
	Mikkel Thorup , Uri Zwick, Spanners and emulators with sublinear distance errors, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.802-809, January 22-26, 2006, Miami, Florida
	Michael Elkin , Yuval Emek , Daniel A. Spielman , Shang-Hua Teng, Lower-stretch spanning trees, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Valmir C. Barbosa , Fernando M. N. Miranda , Matheus C. M. Agostini, Cell-centric heuristics for the classification of cellular automata, Parallel Computing, v.32 n.1, p.44-66, January 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
	Rahul Garg , Vijay K. Garg , Yogish Sabharwal, Scalable algorithms for global snapshots in distributed systems, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
	Michael Elkin, A faster distributed protocol for constructing a minimum spanning tree, Journal of Computer and System Sciences, v.72 n.8, p.1282-1308, December, 2006
	Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal , Corentin Travers, Research note: From ♢W to Ω: A simple bounded quiescent reliable broadcast-based transformation, Journal of Parallel and Distributed Computing, v.67 n.1, p.125-129, January, 2007
	Anat Bremler-Barr , Nir Chen , Jussi Kangasharju , Osnat Mokryn , Yuval Shavitt, Bringing order to BGP: decreasing time and message complexity, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Fabian Kuhn , Thomas Moscibroda, Distributed approximation of capacitated dominating sets, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Surender Baswana, Streaming algorithm for graph spanners---single pass and constant processing time per edge, Information Processing Letters, v.106 n.3, p.110-114, April, 2008
	Surender Baswana , Sandeep Sen, A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs, Random Structures & Algorithms, v.30 n.4, p.532-563, July 2007
	T-H. Hubert Chan , Anupam Gupta , Kunal Talwar, Ultra-low-dimensional embeddings for doubling metrics, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.333-342, January 20-22, 2008, San Francisco, California
	Michel Raynal, About logical clocks for distributed systems, ACM SIGOPS Operating Systems Review, v.26 n.1, p.41-48, Jan. 1992
	Whay C. Lee, Topology aggregation for hierarchical routing in ATM networks, ACM SIGCOMM Computer Communication Review, v.25 n.2, p.82-92, April 1995
	R. Cole , O. Zajicek, The APRAM: incorporating asynchrony into the PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.169-178, June 18-21, 1989, Santa Fe, New Mexico, United States
	Michael Elkin, A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Ad hoc networks beyond unit disk graphs, Wireless Networks, v.14 n.5, p.715-729, October 2008
	Christian Boulinier , Ajoy K. Datta , Lawrence L. Larmore , Franck Petit, Space efficient and time optimal distributed BFS tree construction, Information Processing Letters, v.108 n.5, p.273-278, November, 2008
	Beat Gfeller , Elias Vicari, A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Baruch Awerbuch , Rohit Khandekar, Distributed network monitoring and multicommodity flows: a primal-dual approach, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Costas Busch , Ryan LaFortune , Srikanta Tirthapura, Improved sparse covers for graphs excluding a fixed minor, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Bilel Derbel , Cyril Gavoille, Fast deterministic distributed algorithms for sparse spanners, Theoretical Computer Science, v.399 n.1-2, p.83-100, June, 2008
	Bilel Derbel , Cyril Gavoille , David Peleg , Laurent Viennot, On the locality of distributed sparse spanner construction, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Stefan Eckhardt , Sven Kosub , Moritz G. Maaβ , Hanjo Täubig , Sebastian Wernicke, Combinatorial network abstraction by trees and distances, Theoretical Computer Science, v.407 n.1-3, p.1-20, November, 2008
	Baruch Awerbuch , Shay Kutten , Yishay Mansour , Boaz Patt-Shamir , George Varghese, A Time-Optimal Self-Stabilizing Synchronizer Using A Phase Clock, IEEE Transactions on Dependable and Secure Computing, v.4 n.3, p.180-190, July 2007
	Baruch Awerbuch , Israel Cidon , Shay Kutten, Optimal maintenance of a spanning tree, Journal of the ACM (JACM), v.55 n.4, p.1-45, September 2008
	Yusuke Takahashi , Taisuke Izumi , Hirotsugu Kakugawa , Toshimitsu Masuzawa, An Efficient Index Dissemination in Unstructured Peer-to-Peer Networks, IEICE - Transactions on Information and Systems, v.E91-D n.7, p.1971-1981, July 2008
	Giorgio Ausiello , Paolo G. Franciosa , Giuseppe F. Italiano, Small stretch (α,β)-spanners in the streaming model, Theoretical Computer Science, v.410 n.36, p.3406-3413, August, 2009
	Anat Bremler-Barr , Nir Chen , Jussi Kangasharju , Osnat Mokryn , Yuval Shavitt, Bringing order to BGP: Decreasing time and message complexity, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.53 n.12, p.2241-2256, August, 2009
	Fabian Kuhn, Weak graph colorings: distributed algorithms and applications, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada
	Christoph Lenzen , Thomas Locher , Roger Wattenhofer, Tight bounds for clock synchronization, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
C. Computer Systems Organization

General Terms:
Algorithms, Measurement, Performance, Theory, Verification

REVIEW

"David B. Skillicorn : Reviewer"

This paper presents a method of simulating a synchronous network using an asynchronous network. This is done by means of a synchronizer that generates “clock pulses” at each node on receipt of all messages that should have arrived du more...

Collaborative Colleagues:

Baruch Awerbuch: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player