Show simple item record

dc.contributor.author
Das Sarma, Atish
dc.contributor.author
Holzer, Stephan
dc.contributor.author
Kor, Liah
dc.contributor.author
Nanongkai, Danupon
dc.contributor.author
Pandurangan, Gopal
dc.contributor.author
Peleg, David
dc.contributor.author
Wattenhofer, Roger
dc.date.accessioned
2017-06-09T08:05:20Z
dc.date.available
2017-06-09T08:05:20Z
dc.date.issued
2010-11
dc.identifier.uri
http://hdl.handle.net/20.500.11850/26448
dc.description.abstract
We study the verification problem in distributed networks, stated as follows. Let H be a subgraph of a network G where each vertex of G knows which edges incident on it are in H. We would like to verify whether H has some properties, e.g., if it is a tree or if it is connected. We would like to perform this verification in a decentralized fashion via a distributed algorithm. The time complexity of verification is measured as the number of rounds of distributed communication. <br/>In this paper we initiate a systematic study of distributed verification, and give almost tight lower bounds on the running time of distributed verification algorithms for many fundamental problems such as connectivity, spanning connected subgraph, and s−t cut verification. We then show applications of these results in deriving strong unconditional time lower bounds on the hardness of distributed approximation for many classical optimization problems including minimum spanning tree, shortest paths, and minimum cut. Many of these results are the first non-trivial lower bounds for both exact and approximate distributed computation and they resolve previous open questions. Moreover, our unconditional lower bound of approximating minimum spanning tree (MST) subsumes and improves upon the previous hardness of approximation bound of Elkin [STOC 2004] as well as the lower bound for (exact) MST computation of Peleg and Rubinovich [FOCS 1999]. Our result implies that there can be no distributed approximation algorithm for MST that is significantly faster than the current exact algorithm, for any approximation factor. <br/>Our lower bound proofs show an interesting connection between communication complexity and distributed computing which turns out to be useful in establishing the time complexity of exact and approximate distributed computation of many problems.
dc.language.iso
en
dc.publisher
Cornell University
dc.title
Distributed Verification and Hardness of Distributed Approximation
dc.type
Working Paper
ethz.pages.start
arXiv:1011.3049
ethz.size
31 p.
ethz.notes
Submitted on 12 November 2010.
ethz.publication.place
Ithaca, NY
ethz.publication.status
published
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
ethz.identifier.url
http://arxiv.org/abs/1011.3049
ethz.date.deposited
2017-06-09T08:05:28Z
ethz.source
ECIT
ethz.identifier.importid
imp59364d68cd8db31743
ethz.ecitpid
pub:44954
ethz.eth
yes
ethz.availability
Metadata only
ethz.rosetta.installDate
2017-07-13T07:49:08Z
ethz.rosetta.lastUpdated
2018-10-01T10:14:29Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&amp;rft_val_fmt=info:ofi/fmt:kev:mtx:journal&amp;rft.atitle=Distributed%20Verification%20and%20Hardness%20of%20Distributed%20Approximation&amp;rft.date=2010-11&amp;rft.spage=arXiv:1011.3049&amp;rft.au=Das%20Sarma,%20Atish&amp;Holzer,%20Stephan&amp;Kor,%20Liah&amp;Nanongkai,%20Danupon&amp;Pandurangan,%20Gopal&amp;rft.genre=preprint&amp;rft.btitle=Distributed%20Verification%20and%20Hardness%20of%20Distributed%20Approximation
 Search via SFX

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record