###### Options

# Brief announcement : self-stabilizing MIS computation in the beeping model

Publikationstyp

Conference Paper

Publikationsdatum

2024-06-17

Sprache

English

Start Page

87

End Page

90

Citation

43rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2024)

Contribution to Conference

Publisher DOI

Scopus ID

Publisher

ACM

ISBN

9798400706684

We consider self-stabilizing algorithms to compute a Maximal Independent Set (MIS) in the extremely weak beeping communication model. The model consists of an anonymous network with synchronous rounds. In each round, each vertex can optionally transmit a signal to all its neighbors (beep). After the transmission of a signal, each vertex can only differentiate between no signal received, or at least one signal received. We assume that vertices have some knowledge about the topology of the network.We revisit the not self-stabilizing algorithm proposed by Jeavons, Scott, and Xu (2013), which computes an MIS in the beeping model. We enhance this algorithm to be self-stabilizing, and explore two different variants, which differ in the knowledge about the topology available to the vertices. In the first variant, every vertex knows an upper bound on the maximum degree Δof the graph. For this case, we prove that the proposed self-stabilizing version maintains the same run-time as the original algorithm, i.e. it stabilizes after O(log n) rounds w.h.p. on any n-vertex graph. In the second variant, each vertex only knows an upper bound on its own degree. For this case, we prove that the algorithm stabilizes after O(log n · log log n) rounds on any n-vertex graph, w.h.p.