5 papers
Introducing the Self-Stabilizing SLEEPING Model
Tistou Fages, Colette Johnen, Mikaël Rabie
The SLEEPING LOCAL model introduces a new complexity parameter, the awake complexity, to make distributed algorithms energy-efficient. In the synchronous LOCAL model, nodes can now…
Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost
Alkida Balliu, Pierre Fraigniaud, Dennis Olivetti +1
We study the awake complexity of graph problems that belong to the class O-LOCAL, which includes a subset of problems solvable by sequential greedy algorithms, such as -col…
Asynchronous Fault-Tolerant Distributed Proper Coloring of Graphs
Alkida Balliu, Pierre Fraigniaud, Patrick Lambein-Monette +2
We revisit asynchronous computing in networks of crash-prone processes, under the asynchronous variant of the standard LOCAL model, recently introduced by Fraigniaud et al. [DISC 2…
Shared Randomness Helps with Local Distributed Problems
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn +5
By prior work, we have many results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is loca…
Distributed Coloring in the SLEEPING Model
Fabien Dufoulon, Pierre Fraigniaud, Mikaël Rabie +1
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 w…