logo EDITE Zohir BOUZID
Identité
Zohir BOUZID
État académique
Thèse soutenue le 2013-06-21
Sujet: Modèles et Algorithmes pour les Systèmes Emergents
Direction de thèse:
Encadrement de thèse:
Laboratoire:
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:1298823142206
Optimal Byzantine-resilient Convergence in Unidimensional Robot Networks
Given a set of robots with arbitrary initial location and no agreement on a global coordinate system, convergence requires that all robots asymptotically approach the exact same, but unknown beforehand, location. Robots are oblivious--- they do not recall the past computations --- and are allowed to move in a one-dimensional space. Additionally, robots cannot communicate directly, instead they obtain system related information only via visual sensors.
2010
http://www.springerlink.com/content/a84060167n05065k/
Byzantine-resilient Convergence in Oblivious Robot Networks
Given a set of robots with arbitrary initial location and no agreement
International Conference on Distributed Systems and Networks (ICDCN 2009) 2009
http://arxiv.org/abs/0908.0390
Byzantine Convergence in Robots Networks: The Price of Asynchrony
We study the convergence problem in fully asynchronous, uni-dimensional robot networks that are prone to Byzantine (i.e. malicious) failures. In these settings, oblivious anonymous robots with arbitrary initial positions are required to eventually converge to an a apriori unknown position despite a subset of them exhibiting Byzantine behavior. Our contribution is twofold. We propose a deterministic algorithm that solves the problem in the most generic settings: fully asynchronous robots that operate in the non-atomic CORDA model. Our algorithm provides convergence in 5f+1-sized networks where f is the upper bound on the number of Byzantine robots. Additionally, we prove that 5f+1 is a lower bound whenever robot scheduling is fully asynchronous. This constrasts with previous results in partially synchronous robots networks, where 3f+1 robots are necessary and sufficient.
CoRR, Nimes, France 2009
http://arxiv.org/abs/0906.0651
Optimal Byzantine Resilient Convergence in Asynchronous Robot Networks
We propose the first deterministic algorithm that tolerates up to f byzantine faults in 3f+1-sized networks and performs in the asynchronous CORDA model. Our solution matches the previously established lower bound for the semi-synchronous ATOM model on the number of tolerated Byzantine robots. Our algorithm works under bounded scheduling assumptions for oblivious robots moving in a uni-dimensional space.
Proceedings of SSS 2009., Lyon, France 2009
http://arxiv.org/abs/0908.0390
Byzantine Convergence in Robots Networks: The Price of Asynchrony
We study the convergence problem in fully asynchronous, uni-dimensional robot networks that are prone to Byzantine (i.e. malicious) failures. In these settings, oblivious anonymous robots with arbitrary initial positions are required to eventually converge to an a apriori unknown position despite a subset of them exhibiting Byzantine behavior. Our contribution is twofold. We propose a deterministic algorithm that solves the problem in the most generic settings: fully asynchronous robots that operate in the non-atomic CORDA model. Our algorithm provides convergence in 5f+1-sized networks where f is the upper bound on the number of Byzantine robots. Additionally, we prove that 5f+1 is a lower bound whenever robot scheduling is fully asynchronous. This constrasts with previous results in partially synchronous robots networks, where 3f+1 robots are necessary and sufficient.
PhD thesis 2009
http://arxiv.org/abs/0906.0651
Optimal Byzantine Resilient Convergence in Asynchronous Robot Networks
We propose the first deterministic algorithm that tolerates up to f byzantine faults in 3f+1-sized networks and performs in the asynchronous CORDA model. Our solution matches the previously established lower bound for the semi-synchronous ATOM model on the number of tolerated Byzantine robots. Our algorithm works under bounded scheduling assumptions for oblivious robots moving in a uni-dimensional space.
PhD thesis 2009
http://arxiv.org/abs/0905.3967
Optimal byzantine resilient convergence in oblivious robot networks
Given a set of robots with arbitrary initial location and no agreement on a global coordinate system, convergence requires that all robots asymptotically approach the exact same, but unknown beforehand, location. Robots are oblivious-- they do not recall the past computations -- and are allowed to move in a one-dimensional space. Additionally, robots cannot communicate directly, instead they obtain system related information only via visual sensors. We draw a connection between the convergence problem in robot networks, and the distributed approximate agreement problem (that requires correct processes to decide, for some constant epsilon, values distance epsilon apart and within the range of initial proposed values). Surprisingly, even though specifications are similar, the convergence implementation in robot networks requires specific assumptions about synchrony and Byzantine resilience. In more details, we prove necessary and sufficient conditions for the convergence of mobile robots despite a subset of them being Byzantine (i.e. they can exhibit arbitrary behavior). Additionally, we propose a deterministic convergence algorithm for robot networks and analyze its correctness and complexity in various synchrony settings. The proposed algorithm tolerates f Byzantine robots for (2f+1)-sized robot networks in fully synchronous networks, (3f+1)-sized in semi-synchronous networks. These bounds are optimal for the class of cautious algorithms, which guarantee that correct robots always move inside the range of positions of the correct robots.
PhD thesis 2009
edite:1298823148576
Byzantine-Resilient Convergence in Oblivious Robot Networks
ICDCN 2009
edite:1298823148577
Byzantine Convergence in Robot Networks: The Price of Asynchrony
OPODIS 2009
edite:1298823148578
Optimal Byzantine Resilient Convergence in Asynchronous Robots Networks
SSS 2009
edite:1298823149619
Optimal Byzantine-resilient convergence in uni-dimensional robot networks
Vol. 411, No. 34-36, pp. 3154-3168 2010
http://arxiv.org/abs/1106.0113
Brief Announcement: The BG-simulation for Byzantine Mobile Robots
This paper investigates the task solvability of mobile robot systems subject to Byzantine faults. We first consider the gathering problem, which requires all robots to meet in finite time at a non-predefined location. It is known that the solvability of Byzantine gathering strongly depends on a number of system attributes, such as synchrony, the number of Byzantine robots, scheduling strategy, obliviousness, orientation of local coordinate systems and so on. However, the complete characterization of the attributes making Byzantine gathering solvable still remains open. In this paper, we show strong impossibility results of Byzantine gathering. Namely, we prove that Byzantine gathering is impossible even if we assume one Byzantine fault, an atomic execution system, the n-bounded centralized scheduler, non-oblivious robots, instantaneous movements and a common orientation of local coordinate systems (where n denote the number of correct robots). Those hypotheses are much weaker than used in previous work, inducing a much stronger impossibility result. At the core of our impossibility result is a reduction from the distributed consensus problem in asynchronous shared-memory systems. In more details, we newly construct a generic reduction scheme based on the distributed BG-simulation. Interestingly, because of its versatility, we can easily extend our impossibility result for general pattern formation problems.
Proceedings of DISC 2011, Roma, Italy 2011
http://arxiv.org/abs/1106.0113
The BG-simulation for Byzantine Mobile Robots
This paper investigates the task solvability of mobile robot systems subject to Byzantine faults. We first consider the gathering problem, which requires all robots to meet in finite time at a non-predefined location. It is known that the solvability of Byzantine gathering strongly depends on a number of system attributes, such as synchrony, the number of Byzantine robots, scheduling strategy, obliviousness, orientation of local coordinate systems and so on. However, the complete characterization of the attributes making Byzantine gathering solvable still remains open. In this paper, we show strong impossibility results of Byzantine gathering. Namely, we prove that Byzantine gathering is impossible even if we assume one Byzantine fault, an atomic execution system, the n-bounded centralized scheduler, non-oblivious robots, instantaneous movements and a common orientation of local coordinate systems (where n denote the number of correct robots). Those hypotheses are much weaker than used in previous work, inducing a much stronger impossibility result. At the core of our impossibility result is a reduction from the distributed consensus problem in asynchronous shared-memory systems. In more details, we newly construct a generic reduction scheme based on the distributed BG-simulation. Interestingly, because of its versatility, we can easily extend our impossibility result for general pattern formation problems.
2011
edite:1332792493802
Robocast: Asynchronous Communication in Robot Networks
Proceedings of OPODIS 2010, Tozeur, Tunisia 2010
Soutenance
Thèse: Modèles et Algorithmes pour les Systèmes Émergeants
Soutenance: 2013-06-21
Rapporteurs: Paola FLOCCHINI    Michel RAYNAL