Search

Abstract In this paper, we address the Approximate Agreement problem in the Mobile Byzantine Fault model. Our contribution is three-fold. First, we refine the problem specification to adapt it to the Mobile Byzantine Fault environment. Then, we propose the first mapping from the existing variants of Mobile Byzantine models to the Mixed-mode Fault model. This mapping further help us to prove the correctness of MSR (Mean-Subsequence-Reduce) algorithms class in our context and it is of independent interest. We also prove lower bounds for solving Approximate Agreement under all existing Mobile Byzantine fault models. [ABSTRACT FROM AUTHOR]

Abstract A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced. [ABSTRACT FROM AUTHOR]

The scattering problem is a fundamental task for mobile robots, which requires that no two robots share the same position. We investigate the scattering problem in the limited-visibility model. In particular, we focus on the connectivity-preservation property, i.e. , the scattering must be achieved so that the disconnection of the visibility graph never occurs (in the visibility graph nodes are robots and edges are their visibility relationship). This paper shows a new scattering algorithm in the semi-synchronous model, which guarantees the connectivity preservation property, and reaches a scattered configuration within O ( min ⁡ { n , D 2 + log ⁡ n } ) asynchronous rounds in expectation, where n is the number of robots and D is the diameter of the initial visibility graph. Note that a part of this complexity analysis is adaptive in the sense that it depends on D . This implies that our algorithm quickly scatters all robots crowded with a small-diameter visibility graph. We also show two matching lower bounds for the connectivity-preserving scattering problem. The first lower bound is Ω ( n ) rounds in the case of D = Ω ( n ) , which is a lower bound applying to any connectivity-preserving algorithm. The second bound applies to a (reasonably) restricted class of algorithms, called conservative algorithms , which provides Ω ( D 2 ) -round lower bound. These two bounds imply that our algorithm achieves the optimal running time (in the sense of both adaptive and non-adaptive analyses) as conservative ones because it is conservative. [ABSTRACT FROM AUTHOR]