• View
• Edit
• History
• Print

Application

Reviewer Material

• Curriculum Vitae (PDF)
• Research Perspectives (PDF)
• Abstract collection (PDF)

Selected papers

My research focuses on fault tolerant distributed computing. More precisely, I am interested in self-stabilization. Intuitively, a distributed algorithm is self-stabilizing if, independently from its initial state, it satisfies after finite time its specification. Self-stabilizing algorithms are thus able to tolerate any transient failure that would perturbate the memories of the system components.

1. Self-stabilizing routing in unidirectional networks. Routing, i.e. providing means for two computer that are not directly connected to exchange information, is the main actual application of self-stabilization today. I focused on self-stabilizing routing in unidirectional networks, where it is possible that for a pair of neighboring computers u and v, u can directly send information to v, but the converse is not true.
   • We provided self-stabilizing solutions for unidirectional rings for two low level routing mechanisms, namely Wormhole routing and Cut-through routing. The wormhole solution is the first to investigate self-stabilization in this model, and received the Best paper award in the conference it was presented.
   • We also provided optimal solutions (in terms of stabilization time and overhead) for the case of general unidirectional networks. We defined local operators executed at each node to perform calculus. Depending on properties of the operators, the whole system can be self-stabilizing for any network. The results are somewhat balanced:
     • In the Shared Memory Model, assuming a fair scheduling, a large set of operators can guarantee stabilization (if the network is strongly, connected, the operator is universal, i.e. all static tasks can be solved)
     • In the Read-write Register model and in the Unreliable Message Passing model, a strictly smaller set of operators guarantee stabilization. It is still possible to use this unified approach to construct various kinds of trees and forests (include shortest paths and depth first search). However, in strongly connected networks, there still exists a Universal Algorithm.
2. Self-stabilizing mutual exclusion. Mutual exclusion solutions ensure that accesses to a shared resource are managed such that (i) at most one process is able to access the resource at a given time, and (ii) every requesting process is granted to get access to the resource within finite time. Self-stabilizing mutual exclusion on ring shaped networks is the litterature benchmark for dynamic problems. Our focus in this context was on uniform rings (where all processes execute the same code and are indistinguishable), where it is well known that no deterministic solution exists (for non prime sized rings).
   • We proposed a solution that deals with Unfair scheduling, i.e. the relative speeds of the processors are unknown and unbounded. This solution is the first to provide finite service time (i.e. maximum time between two consecutive accesses to the shared resource) while coping with arbitrary scheduling. The journal version of this paper won the Wilkes runner up award from the British Computer Society, that distinguishes papers published in a volume of The Computer Journal.
   • All existing solutions for uniform self-stabilizing mutual exclusion on ring networks had O(n²) expected stabilization time. We proposed an Optimal Solution that has O(n) expected stabilization time, O(n) expected service time, and O(1) space complexity. All bounds are asymptotically optimal.
   • We proposed a generalization of the problem of mutual exclusion, where up to 'l' resources can be accessed simultaneously, called the l-Exclusion. We focused on maintainting small memory footprint while coping with unfair scheduling.
3. Large-scale stabilization. Although we provided solutions for unidirectional routing and mutual exclusion that are optimal with respect to stabilization time, they are still not scalable, since the stabilization time is in the order of the diameter of the network. To circumvent those limitations, several approaches are possible:
   • time-adaptive stabilization: those are algorithms whose stabilization time is related only to the actual number of faults that hit the system, and not the size of the network. Thus, the lower the number of faults, the faster the recovery. In this context, we proved a Lower Bound on asynchronous time-adaptive stabilization, that essentially shows that step complexity is not appropriate in this context, and we proposed a K-time Adaptive uniform algorithm for mutual exclusion in unidirectional rings that tolerates up to k faults. This results shows that the classes of problems that can be solved by self-stabilizing algorithms and by k-time adaptive algorithms are strictly distinct. Also, we provided a classification of tasks and algorithms according to the possibility to detect Transient Faults.
   • predicate-preserving stabilization: we differentiate failures from normal evolutions of the system (change of costs on links for example). Then, we are able to preserve predicates for normal changes after stabilization. In this context, we proposed a Route Preserving stabilizing algorithm. This last property means that, a tree being constructed towards a particular node called the root, any message sent to the root is received within bounded time, even in the presence of continuous edge cost changes.
   • local stabilization: some problems can be expressed in a localized way (for example, Coloring the nodes of a networks such that neighboring nodes do not have the same color). For those problems, it is possible to design localized algorithms, whose stabilization time is independent of the stabilization time of other parts of the network. We proposed local algorithms for various problems, with various fault tolerance abilities:
     • Probabilistic local stabilization: we developed several probabilistic algorithms in the context of sensor networks. First, a TDMA schedule construction algorithm was presented. A part of this algorithm, based on a randomized coloring, was then used for Clustering purposes. A Complexity Study was also carried out.
     • Snap stabilization: snap-stabilizing systems are systems that immediately match their specification. We designed a snap-stabilizing algorithm for Neighborhood Synchronization in tree structured networks. This algorithm has the noticeable property of only admitting legitimate configurations.
     • Byzantine containment: we designed a self-stabilizing Link Coloring algorithm that also contains an arbitrary number of Byzantine processors. Indeed, the subsystem composed of correct processes manages to color all edges properly and independently of the malicious actions of Byzantine nodes.
4. Mobile agents. Although not strictly related to self-stabilization, mobile agents (or mobile robots) are a nice abstraction for many practical purposes. We concentrated on the traversal problem (i.e. having the mobile agent traverse all edges of an unknown network). We proposed a space optimal traversal algorithm for directed Eulerian networks, and both Lower Bounds and an algorithm for undirected arbitrary graphs.
5. Distributed Fault Injection. With the advent of large scale-systems, faults and malicious behavior are more likely to occur. However, distributed applications are usually tested in reliable clusters of grids before being launched on the Internet. We proposed a software tool to Inject Faults in a distributed and reproducible way. Our tool can also inject faults in Java Applications, which enable testing current implementations of Distributed Hash Tables against coordinated failures. The ultimate goal of our tool is a complete Dependability Benchmarking suite.