Distributed Verification and Hardness of Distributed Approximation - Computer Science > Distributed, Parallel, and Cluster ComputingReportar como inadecuado




Distributed Verification and Hardness of Distributed Approximation - Computer Science > Distributed, Parallel, and Cluster Computing - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We study the {\em verification} problem in distributed networks, stated asfollows. Let $H$ be a subgraph of a network $G$ where each vertex of $G$ knowswhich edges incident on it are in $H$. We would like to verify whether $H$ hassome properties, e.g., if it is a tree or if it is connected. We would like toperform this verification in a decentralized fashion via a distributedalgorithm. The time complexity of verification is measured as the number ofrounds of distributed communication. In this paper we initiate a systematicstudy of distributed verification, and give almost tight lower bounds on therunning time of distributed verification algorithms for many fundamentalproblems such as connectivity, spanning connected subgraph, and $s-t$ cutverification. We then show applications of these results in deriving strongunconditional time lower bounds on the {\em hardness of distributedapproximation} for many classical optimization problems including minimumspanning tree, shortest paths, and minimum cut. Many of these results are thefirst non-trivial lower bounds for both exact and approximate distributedcomputation and they resolve previous open questions. Moreover, ourunconditional lower bound of approximating minimum spanning tree MST subsumesand improves upon the previous hardness of approximation bound of Elkin STOC2004 as well as the lower bound for exact MST computation of Peleg andRubinovich FOCS 1999. Our result implies that there can be no distributedapproximation algorithm for MST that is significantly faster than the currentexact algorithm, for {\em any} approximation factor. Our lower bound proofsshow an interesting connection between communication complexity and distributedcomputing which turns out to be useful in establishing the time complexity ofexact and approximate distributed computation of many problems.



Autor: Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer

Fuente: https://arxiv.org/







Documentos relacionados