Tight Mobile Byzantine Tolerant Atomic Storage

This paper proposes the first implementation of an atomic storage tolerant to mobile Byzantine agents. Our implementation is designed for the round-based synchronous model where the set of Byzantine nodes changes from round to round. In this model we explore the feasibility of multi-writer multi-reader atomic register prone to various mobile Byzantine behaviors. We prove upper and lower bounds for solving the atomic storage in all the explored models. Our results, significantly different from the static case, advocate for a deeper study of the main building blocks of distributed computing while the system is prone to mobile Byzantine failures.

Emergent velocity agreement in robot networks

In this paper we propose and prove correct a new self-stabilizing velocity agreement (flocking) algorithm for oblivious and asynchronous robot networks. Our algorithm allows a flock of uniform robots to follow a flock head emergent during the computation whatever its direction in plane. Robots are asynchronous, oblivious and do not share a common coordinate system. Our solution includes three modules architectured as follows: creation of a common coordinate system that also allows the emergence of a flock-head, setting up the flock pattern and moving the flock. The novelty of our approach steams in identifying the necessary conditions on the flock pattern placement and the velocity of the flock-head (rotation, translation or speed) that allow the flock to both follow the exact same head and to preserve the flock pattern. Additionally, our system is self-healing and self-stabilizing. In the event of the head leave (the leading robot disappears or is damaged and cannot be recognized by the other robots) the flock agrees on another head and follows the trajectory of the new head. Also, robots are oblivious (they do not recall the result of their previous computations) and we make no assumption on their initial position. The step complexity of our solution is O(n).

Physical expander in Virtual Tree Overlay

In this paper, we propose a new construction of constantdegree expanders motivated by their application in P2P overlay networks and in particular in the design of robust trees overlay. Our key result can be stated as follows. Consider a complete binary tree T and construct a random pairing {Pi} between leaf nodes and internal nodes. We prove that the graph GPi obtained from T by contracting all pairs (leaf-internal nodes) achieves a constant node expansion with high probability. The use of our result in improving the robustness of tree overlays is straightforward. That is, if each physical node participating to the overlay manages a random pair that couples one virtual internal node and one virtual leaf node then the physical-node layer exhibits a constant expansion with high probability. We encompass the difficulty of obtaining this random tree virtualization by proposing a local, selforganizing and churn resilient uniformly-random pairing algorithm with O(log2 n) running time. Our algorithm has the merit to not modify the original tree virtual overlay (we just control the mapping between physical nodes and virtual nodes). Therefore, our scheme is general and can be applied to a large number of tree overlay implementations. We validate its performances in dynamic environments via extensive simulations.

A framework for proving the self-organization of dynamic systems

This paper aims at providing a rigorous definition of self- organization, one of the most desired properties for dynamic systems (e.g., peer-to-peer systems, sensor networks, cooperative robotics, or ad-hoc networks). We characterize different classes of self-organization through liveness and safety properties that both capture information re- garding the system entropy. We illustrate these classes through study cases. The first ones are two representative P2P overlays (CAN and Pas- try) and the others are specific implementations of Omega (the leader oracle) and one-shot query abstractions for dynamic settings. Our study aims at understanding the limits and respective power of existing self-organized protocols and lays the basis of designing robust algorithm for dynamic systems.

Optimal deterministic ring exploration with oblivious asynchronous robots

We consider the problem of exploring an anonymous unoriented ring of size $n$ by $k$ identical, oblivious, asynchronous mobile robots, that are unable to communicate, yet have the ability to sense their environment and take decisions based on their local view. Previous works in this weak scenario prove that $k$ must not divide $n$ for a deterministic solution to exist. Also, it is known that the minimum number of robots (either deterministic or probabilistic) to explore a ring of size $n$ is 4. An upper bound of 17 robots holds in the deterministic case while 4 probabilistic robots are sufficient. In this paper, we close the complexity gap in the deterministic setting, by proving that no deterministic exploration is feasible with less than five robots whenever the size of the ring is even, and that five robots are sufficient for any $n$ that is coprime with five. Our protocol completes exploration in O(n) robot moves, which is also optimal.

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.

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 emph{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.