salle A. Turing CE4
23 February 2012 - 14h00
Strength of Stabilization vs. Amount of Resources
by Franck Petit from LIP6
Abstract: The amount of resources used to perform a given task is a key feature in distributed systems, especially when resource embedding is very costly. Ad hoc and sensors networks belong to this category of distributed systems because they are supposed to be made of low-power tiny devices, requiring the smallest amount of resources as possible. Furthermore, such networks are expected to be larger and larger, while the devices are more and more fragile and tiny.
From the algorithmic aspect, it becomes crucial to obtain distributed solutions that are scalable, saving a maximum of energy by using as few resources as possible, with maximum autonomy, i.e., requiring the minimum of human intervention. It is also very desirable that the proposed algorithms tolerate transient dysfunctions due to lack of energy power.
Self-stabilizing algorithms are likely to meet all these requirements together. During this talk, we present some of these algorithms. We focus on synchronization and resource allocation problems. We also show that if the requirements outlined above are often desired performance criteria, they are sometimes required to achieve stabilization.