Source author record

Sébastien Bouchard

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs

A mobile agent navigating along edges of a simple connected graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch, Betke, Rivest and Singh [3] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node $s$ . The size of the tank is $B=2(1+α)r$ , for some positive real constant $α$ , where $r$ , called the radius of the graph, is the maximum distance from $s$ to any other node. The tank of size $B$ allows the agent to make at most $\lfloor B\rfloor$ edge traversals between two consecutive visits at node $s$ . Let $e(d)$ be the number of edges whose at least one extremity is at distance less than $d$ from $s$ . Awerbuch, Betke, Rivest and Singh [3] conjectured that it is impossible to find a treasure hidden in a node at distance at most $d$ at cost nearly linear in $e(d)$ . We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost $\mathcal{O}(e(d) \log d)$ , and then show how to modify this algorithm to work in the model from [3] with the same complexity. Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost $Θ(e(d))$ for all graphs and thus our algorithms are also almost optimal.

preprint2020arXiv

Almost Universal Anonymous Rendezvous in the Plane

Two mobile agents represented by points freely moving in the plane and starting at two distinct positions, have to meet. The meeting, called rendezvous, occurs when agents are at distance at most $r$ of each other and never move after this time, where $r$ is a positive real unknown to them, called the visibility radius. Agents are anonymous and execute the same deterministic algorithm. Each agent has a set of private attributes, some or all of which can differ between agents. These attributes are: the initial position of the agent, its system of coordinates (orientation and chirality), the rate of its clock, its speed when it moves, and the time of its wake-up. If all attributes (except the initial positions) are identical and agents start at distance larger than $r$ then they can never meet. However, differences between attributes make it sometimes possible to break the symmetry and accomplish rendezvous. Such instances of the rendezvous problem (formalized as lists of attributes), are called feasible. Our contribution is three-fold. We first give an exact characterization of feasible instances. Thus it is natural to ask whether there exists a single algorithm that guarantees rendezvous for all these instances. We give a strong negative answer to this question: we show two sets $S_1$ and $S_2$ of feasible instances such that none of them admits a single rendezvous algorithm valid for all instances of the set. On the other hand, we construct a single algorithm that guarantees rendezvous for all feasible instances outside of sets $S_1$ and $S_2$ . We observe that these exception sets $S_1$ and $S_2$ are geometrically very small, compared to the set of all feasible instances: they are included in low-dimension subspaces of the latter. Thus, our rendezvous algorithm handling all feasible instances other than these small sets of exceptions can be justly called almost universal.

preprint2020arXiv

Deterministic Treasure Hunt in the Plane with Angular Hints

A mobile agent equipped with a compass and a measure of length has to find an inert treasure in the Euclidean plane. Both the agent and the treasure are modeled as points. In the beginning, the agent is at a distance at most $D>0$ from the treasure, but knows neither the distance nor any bound on it. Finding the treasure means getting at distance at most 1 from it. The agent makes a series of moves. Each of them consists in moving straight in a chosen direction at a chosen distance. In the beginning and after each move the agent gets a hint consisting of a positive angle smaller than $2π$ whose vertex is at the current position of the agent and within which the treasure is contained. We investigate the problem of how these hints permit the agent to lower the cost of finding the treasure, using a deterministic algorithm, where the cost is the worst-case total length of the agent's trajectory. It is well known that without any hint the optimal (worst case) cost is $Θ(D^2)$ . We show that if all angles given as hints are at most $π$ , then the cost can be lowered to $O(D)$ , which is optimal. If all angles are at most $β$ , where $β<2π$ is a constant unknown to the agent, then the cost is at most $O(D^{2-ε})$ , for some $ε>0$ . For both these positive results we present deterministic algorithms achieving the above costs. Finally, if angles given as hints can be arbitrary, smaller than $2π$ , then we show that cost $Θ(D^2)$ cannot be beaten.

preprint2015arXiv

Byzantine Gathering in Networks

This paper investigates an open problem introduced in [14]. Two or more mobile agents start from different nodes of a network and have to accomplish the task of gathering which consists in getting all together at the same node at the same time. An adversary chooses the initial nodes of the agents and assigns a different positive integer (called label) to each of them. Initially, each agent knows its label but does not know the labels of the other agents or their positions relative to its own. Agents move in synchronous rounds and can communicate with each other only when located at the same node. Up to f of the agents are Byzantine. A Byzantine agent can choose an arbitrary port when it moves, can convey arbitrary information to other agents and can change its label in every round, in particular by forging the label of another agent or by creating a completely new one. What is the minimum number M of good agents that guarantees deterministic gathering of all of them, with termination? We provide exact answers to this open problem by considering the case when the agents initially know the size of the network and the case when they do not. In the former case, we prove M=f+1 while in the latter, we prove M=f+2. More precisely, for networks of known size, we design a deterministic algorithm gathering all good agents in any network provided that the number of good agents is at least f+1. For networks of unknown size, we also design a deterministic algorithm ensuring the gathering of all good agents in any network but provided that the number of good agents is at least f+2. Both of our algorithms are optimal in terms of required number of good agents, as each of them perfectly matches the respective lower bound on M shown in [14], which is of f+1 when the size of the network is known and of f+2 when it is unknown.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.