Dynamic Maximal Matching in Clique Networks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910310015696896 |
|---|---|
| author | Li, Minming Robinson, Peter Zhu, Xianbin |
| author_facet | Li, Minming Robinson, Peter Zhu, Xianbin |
| contents | We consider the problem of computing a maximal matching with a distributed algorithm in the presence of batch-dynamic changes to the graph topology. We assume that a graph of $n$ nodes is vertex-partitioned among $k$ players that communicate via message passing. Our goal is to provide an efficient algorithm that quickly updates the matching even if an adversary determines batches of $\ell$ edge insertions or deletions.
Assuming a link bandwidth of $O(β\log n)$ bits per round, for a parameter $β\ge 1$, we first show a lower bound of $Ω( \frac{\ell\,\log k}{β\,k^2\log n})$ rounds for recomputing a matching assuming an oblivious adversary who is unaware of the initial (random) vertex partition as well as the current state of the players, and a stronger lower bound of $Ω(\frac{\ell}{β\,k\log n})$ rounds against an adaptive adversary, who may choose any balanced (but not necessarily random) vertex partition initially and who knows the current state of the players.
We also present a randomized algorithm that has an initialization time of $O( \lceil\frac{n}{β\,k}\rceil\log n )$ rounds, while achieving an update time that that is independent of $n$: In more detail, the update time is $O( \lceil \frac{\ell}{β\,k} \rceil \log(β\,k))$ against an oblivious adversary, who must fix all updates in advance. If we consider the stronger adaptive adversary, the update time becomes $O( \lceil \frac{\ell}{\sqrt{β\,k}}\rceil \log(β\,k))$ rounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_15550 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dynamic Maximal Matching in Clique Networks Li, Minming Robinson, Peter Zhu, Xianbin Distributed, Parallel, and Cluster Computing Data Structures and Algorithms We consider the problem of computing a maximal matching with a distributed algorithm in the presence of batch-dynamic changes to the graph topology. We assume that a graph of $n$ nodes is vertex-partitioned among $k$ players that communicate via message passing. Our goal is to provide an efficient algorithm that quickly updates the matching even if an adversary determines batches of $\ell$ edge insertions or deletions. Assuming a link bandwidth of $O(β\log n)$ bits per round, for a parameter $β\ge 1$, we first show a lower bound of $Ω( \frac{\ell\,\log k}{β\,k^2\log n})$ rounds for recomputing a matching assuming an oblivious adversary who is unaware of the initial (random) vertex partition as well as the current state of the players, and a stronger lower bound of $Ω(\frac{\ell}{β\,k\log n})$ rounds against an adaptive adversary, who may choose any balanced (but not necessarily random) vertex partition initially and who knows the current state of the players. We also present a randomized algorithm that has an initialization time of $O( \lceil\frac{n}{β\,k}\rceil\log n )$ rounds, while achieving an update time that that is independent of $n$: In more detail, the update time is $O( \lceil \frac{\ell}{β\,k} \rceil \log(β\,k))$ against an oblivious adversary, who must fix all updates in advance. If we consider the stronger adaptive adversary, the update time becomes $O( \lceil \frac{\ell}{\sqrt{β\,k}}\rceil \log(β\,k))$ rounds. |
| title | Dynamic Maximal Matching in Clique Networks |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2401.15550 |