Distributed Coloring in the SLEEPING Model
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_ | 1866913352764096512 |
|---|---|
| author | Dufoulon, Fabien Fraigniaud, Pierre Rabie, Mikaël Zheng, Hening |
| author_facet | Dufoulon, Fabien Fraigniaud, Pierre Rabie, Mikaël Zheng, Hening |
| contents | In distributed network computing, a variant of the LOCAL model has been recently introduced, referred to as the SLEEPING model. In this model, nodes have the ability to decide on which round they are awake, and on which round they are sleeping. Two (adjacent) nodes can exchange messages in a round only if both of them are awake in that round. The SLEEPING model captures the ability of nodes to save energy when they are sleeping. In this framework, a major question is the following: is it possible to design algorithms that are energy efficient, i.e., where each node is awake for a few number of rounds only, without losing too much on the time efficiency, i.e., on the total number of rounds? This paper answers positively to this question, for one of the most fundamental problems in distributed network computing, namely $(Δ+1)$-coloring networks of maximum degree $Δ$. We provide a randomized algorithm with average awake-complexity constant, maximum awake-complexity $O(\log\log n)$ in $n$-node networks, and round-complexity $poly\!\log n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_10058 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Distributed Coloring in the SLEEPING Model Dufoulon, Fabien Fraigniaud, Pierre Rabie, Mikaël Zheng, Hening Distributed, Parallel, and Cluster Computing In distributed network computing, a variant of the LOCAL model has been recently introduced, referred to as the SLEEPING model. In this model, nodes have the ability to decide on which round they are awake, and on which round they are sleeping. Two (adjacent) nodes can exchange messages in a round only if both of them are awake in that round. The SLEEPING model captures the ability of nodes to save energy when they are sleeping. In this framework, a major question is the following: is it possible to design algorithms that are energy efficient, i.e., where each node is awake for a few number of rounds only, without losing too much on the time efficiency, i.e., on the total number of rounds? This paper answers positively to this question, for one of the most fundamental problems in distributed network computing, namely $(Δ+1)$-coloring networks of maximum degree $Δ$. We provide a randomized algorithm with average awake-complexity constant, maximum awake-complexity $O(\log\log n)$ in $n$-node networks, and round-complexity $poly\!\log n$. |
| title | Distributed Coloring in the SLEEPING Model |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2405.10058 |