logo EDITE Swan DUBOIS
Identité
Swan DUBOIS
État académique
Thèse soutenue le 2011-12-01
Sujet: Tolérer les fautes transitoires, permanentes et intermitentes
Direction de thèse:
Encadrement de thèse:
Laboratoire: personnel permanent
Encadrement de thèses (depuis 2007)
1
Voisinage
Ellipse bleue: doctorant, ellipse jaune: docteur, rectangle vert: permanent, rectangle jaune: HDR. Trait vert: encadrant de thèse, trait bleu: directeur de thèse, pointillé: jury d'évaluation à mi-parcours ou jury de thèse.
Productions scientifiques
edite:1298823142211
Construction auto-stabilisante d'arbre couvrant en depit d'actions malicieuses
Un protocole auto-stabilisant est par nature tol'erant aux fautes transitoires (i.e. de dur'ee finie). Ces derni`eres ann'ees ont vu apparaitre une nouvelle classe de protocoles qui, en plus d'etre auto-stabilisants, tol`erent un nombre limit'e de fautes permanentes. Dans cet article, nous nous int'eressons aux protocoles auto-stabilisants tol'erant des fautes permanentes tr`es s'ev`eres : les fautes byzantines. Nous montrons que, pour certains probl`emes n'admettant pas de solution strictement stabilisante (NA02), il existe toutefois des solutions tol'erant des fautes byzantines si nous d'efinissons un crit`ere de tol'erance moins contraignant.
Proceedings of Algotel 2010, Belle-Dune, France 2010
http://arxiv.org/abs/0904.4615
Brief Announcement: Dynamic FTSS in Asynchronous Systems: the Case of Unison
Distributed fault-tolerance can mask the effect of a limited number of per- manent faults, while self-stabilization provides forward recovery after an arbitrary number of transient fault hit the system. FTSS protocols combine the best of both worlds since they are simultaneously fault-tolerant and self-stabilizing. To date, FTSS solutions either consider static (i.e. fixed point) tasks, or assume synchronous scheduling of the system components. In this paper, we present the first study of dynamic tasks in asynchronous systems, considering the unison problem as a benchmark. Unison can be seen as a local clock syn- chronisation problem as neighbors must maintain digital clocks at most one time unit away from each other, and increment their own clock value infinitely often. We present many im- possiblity results for this difficult problem and propose a FTSS solution when the problem is solvable that exhibits optimal fault containment.
Proceedings of DISC 2009, Elche, Spain 2009
edite:1298823148609
Snap-Stabilizing Linear Message Forwarding
12th International Symposium Stabilization, Safety, and Security of Distributed Systems, SSS 2010
edite:1298823148610
On Byzantine Containment Properties of the \it in 1 Protocol
12th International Symposium Stabilization, Safety, and Security of Distributed Systems, SSS 2010
edite:1298823149613
Brief Announcement: Sharing Memory in a Self-stabilizing Manner
24th International Symposium Distributed Computing DISC 2010
edite:1298823149615
The Impact of Topology on Byzantine Containment in Stabilization
24th International Symposium Distributed Computing DISC 2010
oai:hal.inria.fr:inria-00627780
Pragmatic Self-Stabilization of Atomic Memory in Message-Passing Systems
13th International Symposium on Stabilization, Safety, and Security of Distributed Systemsproceeding with peer review 2011
oai:hal.inria.fr:inria-00383116
Une CNS pour l'acheminement de messages instantanément stabilisant
A snap-stabilizing algorithm ensures that it always behaves according to its specifications whenever it starts from an arbitrary configuration. In this paper, we interest in the message forwarding problem in a message-switched network. We must manage network ressources in order to deliver messages to any processor of the network. In this goal, we need information given by a routing algorithm. But, due to the context of stabilization, this information can be initially corrupted. It is why the existence of snap-stabilizing algorithms for this task (proved in [CDV09]) implies that we can ask the system to begin forwarding messages even if routing tables are initially corrupted. In this paper, we generalize the previous result given a necessary and sufficient condition to solve the forwarding problem in a snap-stabilizing way.
AlgoTelproceeding with peer review 2009
oai:hal.inria.fr:inria-00587089
Communication Optimalement Stabilisante sur Canaux non Fiables et non FIFO
A self-stabilizing protocol has the capacity to recover a legitimate behavior whatever is its initial state. The majority of works in self-stabilization assume a shared memory model or a communication using reliable and FIFO channels. In this article, we interest in self-stabilizing systems using bounded but non reliable and non FIFO channels. We propose a stabilizing communication protocol with optimal fault resilience. In more details, this protocol simulates a reliable and FIFO channel and ensures a minimal number of looses, duplications, creations, and re-ordering of messages.
13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel)proceeding with peer review 2011
oai:hal.inria.fr:inria-00627746
Bounding the Impact of Unbounded Attacks in Stabilization
IEEE Transactions on Parallel and Distributed Systemspeer-reviewed article 2011-05
oai:hal.inria.fr:inria-00627760
Stabilizing data-link over non-FIFO channels with optimal fault-resilience
Information Processing Letterspeer-reviewed article 2011-09
oai:hal.inria.fr:inria-00627763
Dynamic FTSS in asynchronous systems: The case of unison
Theoretical Computer Sciencepeer-reviewed article 2011-07
oai:hal.inria.fr:inria-00627771
Brief Announcement: Self-Stabilizing Byzantine Asynchronous Unison
14th International Conference On Principles Of DIstributed Systemsproceeding with peer review 2010
oai:hal.inria.fr:inria-00627777
Maximum Metric Spanning Tree made Byzantine Tolerant
25th International Symposium on Distributed Computingproceeding with peer review 2011
oai:hal.inria.fr:inria-00587517
Auto-Stabilisation et Confinement de Fautes Malicieuses : Optimalité du Protocole min+1
A self-stabilizing is naturally resilient to transients faults (that is, faults of finite duration). Recently, a new class of protocol appears. These protocols are self-stabilizing and are moreover resilient to a limited number of permanent faults. In this article, we interest in self-stabilizing protocols that tolerate very hard permanent faults: Byzantine faults. We introduce two new scheme of Byzantine containment in self-stabilizing systems. We show that, for the problem of BFS spanning tree construction, the well known self-stabilizing protocol min+1 provides without significant modification the best Byzantine containment with respect to these new schemes.
13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel)proceeding with peer review 2011
oai:hal.inria.fr:inria-00628079
How to improve snap-stabilizing point-to-point communication space complexity?
Journal of Theoretical Computer Science (TCS)peer-reviewed article 2011-07
oai:hal.inria.fr:inria-00628081
How to improve snap-stabilizing point-to-point communication space complexity ?
11th International Symposium on Stabilization, Safety, and Security of Distributed Systemsproceeding with peer review 2009
oai:hal.inria.fr:inria-00628083
A snap-stabilizing point-to-point communication protocol in message-switched networks
23th IEEE International Parallel & Distributed Processing Symposiumproceeding with peer review 2009
oai:hal.inria.fr:inria-00628085
Acheminement de Messages Instantanément Stabilisant : Solution Optimale sur les Topologies Linéaires
Rencontres francophones du Parallélismeproceeding with peer review 2011
oai:hal.inria.fr:inria-00628088
Snap-Stabilizing Message Forwarding Algorithm on Tree Topologies
13th International Conference on Distributed Computing and Networkingproceeding with peer review 2012
edite:133279229828
Snap-Stabilizing Message Forwarding Algorithm on Tree Topologies
13th International Conference on Distributed Computing and Networking (ICDCN 2012), Honk-Kong, China 2012
http://arxiv.org/abs/1104.4022
Auto-Stabilisation et Confinement de Fautes Malicieuses : Optimalit'e du Protocole min 1
CoRR Proceedings of Algotel 2011 2011
edite:1332792337115
Bounding the Impact of Unbounded Attacks in Stabilization
2011
http://arxiv.org/abs/1104.3947
Communication Optimalement Stabilisante sur Canaux non Fiables et non FIFO
CoRR Proceedings of Algotel 2011 2011
edite:1332792352177
Dynamic FTSS in Asynchronous Systems: the Case of Unison
Distributed fault-tolerance can mask the effect of a limited number of per- manent faults, while self-stabilization provides forward recovery after an arbitrary number of transient fault hit the system. FTSS protocols combine the best of both worlds since they are simultaneously fault-tolerant and self-stabilizing. To date, FTSS solutions either consider static (i.e. fixed point) tasks, or assume synchronous scheduling of the system components. In this paper, we present the first study of dynamic tasks in asynchronous systems, considering the unison problem as a benchmark. Unison can be seen as a local clock syn- chronisation problem as neighbors must maintain digital clocks at most one time unit away from each other, and increment their own clock value infinitely often. We present many im- possiblity results for this difficult problem and propose a FTSS solution when the problem is solvable that exhibits optimal fault containment.
Vol. 29 412, pp. 3418-3439 2011
http://arxiv.org/abs/1104.5368
Maximum Metric Spanning Tree made Byzantine Tolerant
Proceedings of DISC 2011, Rome, Italy 2011
edite:1332792400342
Pragmatic Self-Stabilization of Atomic Memory in Message-Passing Systems
A fault-tolerant and stabilizing simulation of an atomic register is presented. The simulation works in asynchronous message-passing systems, and allows a minority of processes to crash. The simulation stabilizes in a pragmatic manner, by reaching a long execution in which it runs correctly. A key element in the simulation is a new combinatorial construction of a bounded labeling scheme accommodating arbitrary labels, including those not generated by the scheme itself.
Proceedings of SSS 2011, Grenoble, France 2011
edite:1332792449566
Construction auto-stabilisante d'arbre couvrant en dépit d'actions malicieuses
Un protocole auto-stabilisant est par nature tol'erant aux fautes transitoires (i.e. de dur'ee finie). Ces derni`eres ann'ees ont vu apparaitre une nouvelle classe de protocoles qui, en plus d'etre auto-stabilisants, tol`erent un nombre limit'e de fautes permanentes. Dans cet article, nous nous int'eressons aux protocoles auto-stabilisants tol'erant des fautes permanentes tr`es s'ev`eres : les fautes byzantines. Nous montrons que, pour certains probl`emes n'admettant pas de solution strictement stabilisante (NA02), il existe toutefois des solutions tol'erant des fautes byzantines si nous d'efinissons un crit`ere de tol'erance moins contraignant.
Proceedings of Algotel 2010, Belle-Dune, France 2010
http://hal.inria.fr/inria-00487091/PDF/DuboisMasuzawaTixeuil.pdf
On Byzantine Containment Properties of the min 1 Protocol
Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors. %X We consider the well known problem of constructing a breadth-first spanning tree in this context. Combining these two properties proves difficult: we demonstrate that it is impossible to contain the impact of Byzantine nodes in a strictly or strongly stabilizing manner. We then adopt the weaker scheme of topology-aware strict stabilization and we present a similar weakening of strong stabilization. We prove that the classical min 1 protocol has optimal Byzantine containment properties with respect to these criteria.
Proceedings of SSS 2010, New York, NY, USA 2010
edite:1332792479726
On Byzantine Containment Properties of the \it in 1 Protocol
12th International Symposium Stabilization, Safety, and Security of Distributed Systems, SSS 2010
http://arxiv.org/abs/0912.0134
Self-Stabilizing Byzantine Asynchronous Unison
We explore asynchronous unison in the presence of systemic transient and permanent Byzantine faults in shared memory. We observe that the problem is not solvable under less than strongly fair scheduler or for system topologies with maximum node degree greater than two. We present a self-stabilizing Byzantine-tolerant solution to asynchronous unison for chain and ring topologies. Our algorithm has minimum possible containment radius and optimal stabilization time.
Proceedings of OPODIS 2010, Tozeur, Tunisia 2010
edite:1332792531994
Brief Announcement: Dynamic FTSS in Asynchronous Systems: The Case of Unison
DISC 2009
Soutenance
Thèse: Tolérer les fautes transitoires, permanentes et intermitentes
Soutenance: 2011-12-01
Rapporteurs: Bertrand DUCOURTHIAL    Ted HERMAN