What cannot be computed locally!

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

What cannot be computed locally!

Full text

Pdf (254 KB)

Source

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

St. John's, Newfoundland, Canada

SESSION: Wireless and sensor table of contents

Pages: 300 - 309

Year of Publication: 2004

ISBN:1-58113-802-4

Authors

Fabian Kuhn	ETH Zurich, Zurich, Switzerland
Thomas Moscibroda	ETH Zurich, Zurich, Switzerland
Roger Wattenhofer	ETH Zurich, Zurich, Switzerland

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 66, Citation Count: 28

Additional Information:

abstract 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/1011767.1011811 What is a DOI?

ABSTRACT

We give time lower bounds for the distributed approximation of minimum vertex cover (MVC) and related problems such as minimum dominating set (MDS). In k communication rounds, MVC and MDS can only be approximated by factors Ω(n^c/k2/k) and Ω(Δ>^1/k/k) for some constant c, where n and Δ denote the number of nodes and the largest degree in the graph. The number of rounds required in order to achieve a constant or even only a polylogarithmic approximation ratio is at least Ω(√log n/log log n) and Ω(logΔ/ log log Δ). By a simple reduction, the latter lower bounds also hold for the construction of maximal matchings and maximal independent sets.

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 , Shay Kutten , Moti Yung, The local detection paradigm and its applications to self-stabilization, Theoretical Computer Science, v.186 n.1-2, p.199-229, Oct. 30, 1997 [doi>10.1016/S0304-3975(96)00286-1]
	2	Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
	3	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
	4	Michael Elkin, Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007407]
	5	Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
	6	Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September 2003 [doi>10.1007/s00446-003-0091-y]
	7	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]
	8	Amos Israel , A. Itai, A fast and simple randomized parallel algorithm for maximal matching, Information Processing Letters, v.22 n.2, p.77-80, 1986 [doi>10.1016/0020-0190(86)90144-4]
	9	Fabian Kuhn , Roger Wattenhofer, Constant-time distributed dominating set approximation, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.25-32, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872040]
	10	F. Kuhn and R. Wattenhofer. Distributed Combinatorial Optimization. Technical Report 426, ETH Zurich, Dept. of Computer Science, 2003.
	11	Eyal Kushilevitz , Yishay Mansour, An $\Omega(D\log (N/D))$ Lower Bound for Broadcast in Radio Networks, SIAM Journal on Computing, v.27 n.3, p.702-712, June 1998 [doi>10.1137/S0097539794279109]
	12	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]
	13	Felix Lazebnik , Vasiliy A. Ustimenko, Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Applied Mathematics, v.60 n.1-3, p.275-284, June 23, 1995 [doi>10.1016/0166-218X(94)00058-L]
	14	F. Lazebnik, V. A. Ustimenko, and A. J. Woldar. A New Series of Dense Graphs of High Girth. Bulletin of the American Mathematical Society (N.S.), 32(1):73--79, 1995.
	15	Nathan Linial, Locality in distributed graph algorithms, SIAM Journal on Computing, v.21 n.1, p.193-201, Feb. 1992 [doi>10.1137/0221015]
	16	Zvi Lotker , Boaz Patt-Shamir , David Peleg, Distributed MST for constant diameter graphs, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.63-71, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383984]
	17	Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
	18	Moni Naor , Larry Stockmeyer, What can be computed locally?, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.184-193, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167149]
	19	David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
	20	David Peleg , Vitaly Rubinovich, A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction, SIAM Journal on Computing, v.30 n.5, p.1427-1442, 2000 [doi>10.1137/S0097539700369740]

CITED BY 28

	Yu Wang , WeiZhao Wang , Xiang-Yang Li, Distributed low-cost backbone formation for wireless ad hoc networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA
	Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Initializing newly deployed ad hoc and sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA
	Thomas Moscibroda , Roger Wattenhofer, Maximal independent sets in radio networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	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
	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
	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
	Xiang-Yang Li , Wen-Zhan Song , Weizhao Wang, A unified energy-efficient topology for unicast and broadcast, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany
	Amos Korman , Shay Kutten , David Peleg, Proof labeling schemes, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, The price of being near-sighted, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.980-989, January 22-26, 2006, Miami, Florida
	Amos Korman , Shay Kutten, Distributed verification of minimum spanning trees, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Fabian Kuhn , Roger Wattenhofer, Constant-time distributed dominating set approximation, Distributed Computing, v.17 n.4, p.303-310, May 2005
	Yitzhak Birk , Idit Keidar , Liran Liss , Assaf Schuster , Ran Wolff, Veracity radius: capturing the locality of distributed computations, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Pierre Fraigniaud , Amos Korman , Emmanuelle Lebhar, Local MST computation with short advice, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, 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
	Idit Keidar , Assaf Schuster, Want scalable computing?: speculate!, ACM SIGACT News, v.37 n.3, September 2006
	Christoph Lenzen , Yvonne Anne Oswald , Roger Wattenhofer, What can be approximated locally?: case study: dominating sets in planar graphs, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	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
	Maleq Khan , Gopal Pandurangan , V. S. Anil Kumar, A simple randomized scheme for constructing low-weight k-connected spanning subgraphs with applications to distributed algorithms, Theoretical Computer Science, v.385 n.1-3, p.101-114, October, 2007
	Bilel Derbel , Cyril Gavoille, Fast deterministic distributed algorithms for sparse spanners, Theoretical Computer Science, v.399 n.1-2, p.83-100, June, 2008
	Johannes Schneider , Roger Wattenhofer, A log-star distributed maximal independent set algorithm for growth-bounded graphs, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Leonid Barenboim , Michael Elkin, Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Maleq Khan , Fabian Kuhn , Dahlia Malkhi , Gopal Pandurangan , Kunal Talwar, Efficient distributed approximation algorithms via probabilistic tree embeddings, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada
	Shlomi Dolev , Nir Tzachar, Empire of colonies: Self-stabilizing and self-organizing distributed algorithm, Theoretical Computer Science, v.410 n.6-7, p.514-532, February, 2009
	Leonid Barenboim , Michael Elkin, Distributed (δ+1)-coloring in linear (in δ) time, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Valentin Polishchuk , Jukka Suomela, A simple local 3-approximation algorithm for vertex cover, Information Processing Letters, v.109 n.12, p.642-645, May, 2009
	Christos Koufogiannakis , Neal E. Young, Distributed and parallel algorithms for weighted vertex cover and other covering problems, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Saurav Pandit , Sriram Pemmaraju, Return of the primal-dual: distributed metric facilitylocation, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada
	Roger Wattenhofer, Algorithms for ad hoc and sensor networks, Computer Communications, v.28 n.13, p.1498-1504, August, 2005