Singing a MIS
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911299572596736 |
|---|---|
| author | Irani, Sandy Luby, Michael |
| author_facet | Irani, Sandy Luby, Michael |
| contents | We introduce a broadcast model called the singing model, where agents are oblivious of the size and structure of the communication network, even their immediate neighborhood. Agents can sing multiple notes which are heard by their neighbors. The model is a generalization of the beeping model, where agents can only emit sound at a single frequency. We give a simple and natural protocol where agents compete with their neighbors and their strength is reflected in the number of notes they sing. It converges in $O(log(n))$ time with high probability, where $n$ is the number of agents in the network. The protocol works in an asynchronous model where rounds vary in length and have different start times. It works with completely dynamic networks where agents can be faulty. The protocol is the first to converge to an MIS in logarithmic time for dynamic networks in a network oblivious model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_03311 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Singing a MIS Irani, Sandy Luby, Michael Data Structures and Algorithms We introduce a broadcast model called the singing model, where agents are oblivious of the size and structure of the communication network, even their immediate neighborhood. Agents can sing multiple notes which are heard by their neighbors. The model is a generalization of the beeping model, where agents can only emit sound at a single frequency. We give a simple and natural protocol where agents compete with their neighbors and their strength is reflected in the number of notes they sing. It converges in $O(log(n))$ time with high probability, where $n$ is the number of agents in the network. The protocol works in an asynchronous model where rounds vary in length and have different start times. It works with completely dynamic networks where agents can be faulty. The protocol is the first to converge to an MIS in logarithmic time for dynamic networks in a network oblivious model. |
| title | Singing a MIS |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.03311 |