The R(1)W(1) Communication Model for Self-Stabilizing Distributed Algorithms
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918154836377600 |
|---|---|
| author | Kakugawa, Hirotsugu Kamei, Sayaka Shibata, Masahiro Ooshita, Fukuhito |
| author_facet | Kakugawa, Hirotsugu Kamei, Sayaka Shibata, Masahiro Ooshita, Fukuhito |
| contents | Self-stabilization is a versatile methodology in the design of fault-tolerant distributed algorithms for transient faults. A self-stabilizing system automatically recovers from any kind and any finite number of transient faults. This property is specifically useful in modern distributed systems with a large number of components. In this paper, we propose a new communication and execution model named the R(1)W(1) model in which each process can read and write its own and neighbors' local variables in a single step. We propose self-stabilizing distributed algorithms in the R(1)W(1) model for the problems of maximal matching, minimal k-dominating set and maximal k-dependent set. Finally, we propose an example transformer, based on randomized distance-two local mutual exclusion, to simulate algorithms designed for the R(1)W(1) model in the synchronous message passing model with synchronized clocks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_04644 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The R(1)W(1) Communication Model for Self-Stabilizing Distributed Algorithms Kakugawa, Hirotsugu Kamei, Sayaka Shibata, Masahiro Ooshita, Fukuhito Distributed, Parallel, and Cluster Computing Self-stabilization is a versatile methodology in the design of fault-tolerant distributed algorithms for transient faults. A self-stabilizing system automatically recovers from any kind and any finite number of transient faults. This property is specifically useful in modern distributed systems with a large number of components. In this paper, we propose a new communication and execution model named the R(1)W(1) model in which each process can read and write its own and neighbors' local variables in a single step. We propose self-stabilizing distributed algorithms in the R(1)W(1) model for the problems of maximal matching, minimal k-dominating set and maximal k-dependent set. Finally, we propose an example transformer, based on randomized distance-two local mutual exclusion, to simulate algorithms designed for the R(1)W(1) model in the synchronous message passing model with synchronized clocks. |
| title | The R(1)W(1) Communication Model for Self-Stabilizing Distributed Algorithms |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2510.04644 |