Mikaël Rabie (IRIF)
Title: An introduction to the SLEEPING model
Abstract:
In distributed computing, one classical model is the LOCAL model: agents (or processors) are on the vertices of a graph, and need to communicate synchronously to solve a problem, such as coloring, maximal independent set, or matching. In particular, the goal is to provide a fast algorithm (usually polylogarithmic) for those problems. Those algorithms make each processor run during the whole computation. However, one might wonder whether it is necessary to have all processors running all the time simultaneously. To save energy, we can let processors ‘‘sleep’’ when they do not need to communicate with their neighbors. In this talk, I will introduce the SLEEPING model, with the new notion of awake complexity. In particular, I will focus on coloring problems and trade-offs between the number of awake rounds per processor and the total number of rounds.