Distributed Algorithms and Applications to Embedded Systems

 People Involved and Related Projects

Projects

• DACRAW
• PADEC
• Collaboration with Orange Labs

People

• Karine Altisen
• Stéphane Devismes
• Florence Maraninchi

 Research Topics

Modern distributed systems can be large-scale, dynamic, and / or resource constrained. These characteristics make them more vulnerable to faults. Now, the scale of these systems as well as the adversarial environment where they may be deployed limit the possibility of human intervention to repair them. In this context, fault-tolerance, i.e., the ability of a distributed algorithm to withstand faults, is mandatory.

Self-stabilization is a versatile lightweight technique to withstand transient faults in a distributed system : a self-stabilizing algorithm recovers correct behavior within finite time after transient faults.

Self-stabilization makes no hypotheses on the nature or extent of transient faults that could hit the system, and recovers from the effects of those faults in a unified manner. Therefore the property of self-stabilization is very attractive for a distributed algorithm.

Wireless Sensors Networks (WSN) are a typical example of distributed systems where self-stabilization is a desirable property. Indeed, in such networks,

• wireless communications are unreliable (due to ultra low power radios) and unstable (because prone to external perturbation) ;
• nodes are subject to crashes because they are supplied with low energy batteries.

We focus on both the theoretical foundation of distributed fault-tolerant algorithms and the design of concrete protocols for embedded systems (e.g., the WSN routing protocol SR3).

Another axis of Research concerns Smart Cities, which are a context where sensors and actuators are deployed for various distributed applications. For the moment the applications are implemented in a vertical way, each stakeholder deploying its own device infrastructure, communication layers, and applications. We work on the notion of horizontalization for smart cities applications, allowing to share devices. This implies, in particular, a standardization of the interfaces, based on automata models. This is a collaboration with Orange Labs.