Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2305.14178 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911792040509440 |
|---|---|
| author | Batu, Tugkan Trehan, Amitabh Trehan, Chhaya |
| author_facet | Batu, Tugkan Trehan, Amitabh Trehan, Chhaya |
| contents | We propose a simple and time-optimal algorithm for property testing a graph for its conductance in the CONGEST model. Our algorithm takes only $O(\log n)$ rounds of communication (which is known to be optimal), and consists of simply running multiple random walks of $O(\log n)$ length from a certain number of random sources, at the end of which nodes can decide if the underlying network is a good conductor or far from it. Unlike previous algorithms, no aggregation is required even with a smaller number of walks. Our main technical contribution involves a tight analysis of this process for which we use spectral graph theory. We introduce and leverage the concept of sticky vertices which are vertices in a graph with low conductance such that short random walks originating from these vertices end in a region around them.
The present state-of-the-art distributed CONGEST algorithm for the problem by Fichtenberger and Vasudev [MFCS 2018], runs in $O(\log n)$ rounds using three distinct phases : building a rooted spanning tree (\emph{preprocessing}), running $O(n^{100})$ random walks to generate statistics (\emph{Phase~1}), and then convergecasting to the root to make the decision (\emph{Phase~2}). The whole of our algorithm is, however, similar to their Phase~1 running only $O(m^2) = O(n^4)$ walks.
Note that aggregation (using spanning trees) is a popular technique but spanning tree(s) are sensitive to node/edge/root failures, hence, we hope our work points to other more distributed, efficient and robust solutions for suitable problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_14178 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Distributed Conductance Tester Without Global Information Collection Batu, Tugkan Trehan, Amitabh Trehan, Chhaya Distributed, Parallel, and Cluster Computing Data Structures and Algorithms We propose a simple and time-optimal algorithm for property testing a graph for its conductance in the CONGEST model. Our algorithm takes only $O(\log n)$ rounds of communication (which is known to be optimal), and consists of simply running multiple random walks of $O(\log n)$ length from a certain number of random sources, at the end of which nodes can decide if the underlying network is a good conductor or far from it. Unlike previous algorithms, no aggregation is required even with a smaller number of walks. Our main technical contribution involves a tight analysis of this process for which we use spectral graph theory. We introduce and leverage the concept of sticky vertices which are vertices in a graph with low conductance such that short random walks originating from these vertices end in a region around them. The present state-of-the-art distributed CONGEST algorithm for the problem by Fichtenberger and Vasudev [MFCS 2018], runs in $O(\log n)$ rounds using three distinct phases : building a rooted spanning tree (\emph{preprocessing}), running $O(n^{100})$ random walks to generate statistics (\emph{Phase~1}), and then convergecasting to the root to make the decision (\emph{Phase~2}). The whole of our algorithm is, however, similar to their Phase~1 running only $O(m^2) = O(n^4)$ walks. Note that aggregation (using spanning trees) is a popular technique but spanning tree(s) are sensitive to node/edge/root failures, hence, we hope our work points to other more distributed, efficient and robust solutions for suitable problems. |
| title | A Distributed Conductance Tester Without Global Information Collection |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2305.14178 |