Search

Your search keyword '"Tixeuil, Sébastien"' showing total 86 results
Start Over Author "Tixeuil, Sébastien" Publication Year Range Last 3 years

Refine your results

more »

more »

more »
86 results on '"Tixeuil, Sébastien"'

1. Swarms of Mobile Robots: Towards Versatility with Safety

Author

Courtieu, Pierre, Rieg, Lionel, Tixeuil, Sébastien, and Urbain, Xavier

Subjects
distributed algorithm, mobile autonomous robots, formal proof, Technology, Electrical engineering. Electronics. Nuclear engineering, TK1-9971, Electronics, TK7800-8360
Abstract

We present Pactole, a formal framework to design and prove the correctness of protocols (or the impossibility of their existence) that target mobile robotic swarms. Unlike previous approaches, our methodology unifies in a single formalism the execution model, the problem specification, the protocol, and its proof of correctness. The Pactole framework makes use of the Coq proof assistant, and is specially targeted at protocol designers and problem specifiers, so that a common unambiguous language is used from the very early stages of protocol development. We stress the underlying framework design principles to enable high expressivity and modularity, and provide concrete examples about how the Pactole framework can be used to tackle actual problems, some previously addressed by the Distributed Computing community, but also new problems, while being certified correct.

Published
2022
Full Text
View/download PDF

2. Elevator: Self-* and Persistent Hub Sampling Service in Unstructured Peer-to-Peer Networks

Author

Legheraba, Mohamed Amine, Potop-Butucaru, Maria, and Tixeuil, Sébastien

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

We present Elevator, a novel algorithm for hub samplingin peer-to-peer networks, enabling the construction of overlays with atopology between a random graph and a star network, and networksthat have both hubs and are resilient to failures. Our approach emergesfrom principles of preferential attachment, forming hubs spontaneously,offering an innovative solution for decentralized networks that can benefituse cases requiring a network with both low diameter and resilience tofailures.

Published
2024

3. Data Poisoning Attacks in Gossip Learning

Author

Pham, Alexandre, Potop-Butucaru, Maria, Tixeuil, Sébastien, and Fdida, Serge

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

Traditional machine learning systems were designed in a centralized manner. In such designs, the central entity maintains both the machine learning model and the data used to adjust the model's parameters. As data centralization yields privacy issues, Federated Learning was introduced to reduce data sharing and have a central server coordinate the learning of multiple devices. While Federated Learning is more decentralized, it still relies on a central entity that may fail or be subject to attacks, provoking the failure of the whole system. Then, Decentralized Federated Learning removes the need for a central server entirely, letting participating processes handle the coordination of the model construction. This distributed control urges studying the possibility of malicious attacks by the participants themselves. While poisoning attacks on Federated Learning have been extensively studied, their effects in Decentralized Federated Learning did not get the same level of attention. Our work is the first to propose a methodology to assess poisoning attacks in Decentralized Federated Learning in both churn free and churn prone scenarios. Furthermore, in order to evaluate our methodology on a case study representative for gossip learning we extended the gossipy simulator with an attack injector module.

Published
2024

4. Stand-Up Indulgent Gathering on Rings

Author

Bramas, Quentin, Kamei, Sayaka, Lamani, Anissa, and Tixeuil, Sébastien

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

We consider a collection of $k \geq 2$ robots that evolve in a ring-shaped network without common orientation, and address a variant of the crash-tolerant gathering problem called the \emph{Stand-Up Indulgent Gathering} (SUIG): given a collection of robots, if no robot crashes, robots have to meet at the same arbitrary location, not known beforehand, in finite time; if one robot or more robots crash on the same location, the remaining correct robots gather at the location of the crashed robots. We aim at characterizing the solvability of the SUIG problem without multiplicity detection capability.

Published
2024

5. Stand-Up Indulgent Gathering on Lines for Myopic Luminous Robots

Author

Bramas, Quentin, Kakugawa, Hirotsugu, Kamei, Sayaka, Lamani, Anissa, Ooshita, Fukuhito, Shibata, Masahiro, and Tixeuil, Sébastien

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

We consider a strong variant of the crash fault-tolerant gathering problem called stand-up indulgent gathering (SUIG), by robots endowed with limited visibility sensors and lights on line-shaped networks. In this problem, a group of mobile robots must eventually gather at a single location, not known beforehand, regardless of the occurrence of crashes. Differently from previous work that considered unlimited visibility, we assume that robots can observe nodes only within a certain fixed distance (that is, they are myopic), and emit a visible color from a fixed set (that is, they are luminous), without multiplicity detection. We consider algorithms depending on two parameters related to the initial configuration: $M_{init}$, which denotes the number of nodes between two border nodes, and $O_{init}$, which denotes the number of nodes hosting robots. Then, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if $M_{init}$ or $O_{init}$ is odd, SUIG can be solved in the fully synchronous model.

Published
2023

6. Reliable Broadcast despite Mobile Byzantine Faults

Author

Bonomi, Silvia, Farina, Giovanni, and Tixeuil, Sébastien

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

We investigate the solvability of the Byzantine Reliable Broadcast and Byzantine Broadcast Channel problems in distributed systems affected by Mobile Byzantine Faults. We show that both problems are not solvable even in one of the most constrained system models for mobile Byzantine faults defined so far. By endowing processes with an additional local failure oracle, we provide a solution to the Byzantine Broadcast Channel problem.

Published
2023

7. Meeting Times of Non-atomic Random Walks

Author

Eguchi, Ryota, Ooshita, Fukuhito, Inoue, Michiko, and Tixeuil, Sébastien

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Discrete Mathematics, Mathematics - Probability
Abstract

In this paper, we revisit the problem of classical \textit{meeting times} of random walks in graphs. In the process that two tokens (called agents) perform random walks on an undirected graph, the meeting times are defined as the expected times until they meet when the two agents are initially located at different vertices. A key feature of the problem is that, in each discrete time-clock (called \textit{round}) of the process, the scheduler selects only one of the two agents, and the agent performs one move of the random walk. In the adversarial setting, the scheduler utilizes the strategy that intends to \textit{maximizing} the expected time to meet. In the seminal papers \cite{collisions,israeli1990token,tetali1993simult}, for the random walks of two agents, the notion of \textit{atomicity} is implicitly considered. That is, each move of agents should complete while the other agent waits. In this paper, we consider and formalize the meeting time of \textit{non-atomic} random walks. In the non-atomic random walks, we assume that in each round, only one agent can move but the move does not necessarily complete in the next round. In other words, we assume that an agent can move at a round while the other agent is still moving on an edge. For the non-atomic random walks with the adversarial schedulers, we give a polynomial upper bound on the meeting times., Comment: 18 pages, 1 figure

Published
2023

8. Stand-Up Indulgent Gathering on Lines

Author

Bramas, Quentin, Kamei, Sayaka, Lamani, Anissa, and Tixeuil, Sébastien

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

We consider a variant of the crash-fault gathering problem called stand-up indulgent gathering (SUIG). In this problem, a group of mobile robots must eventually gather at a single location, which is not known in advance. If no robots crash, they must all meet at the same location. However, if one or more robots crash at a single location, all non-crashed robots must eventually gather at that location. The SUIG problem was first introduced for robots operating in a two-dimensional continuous Euclidean space, with most solutions relying on the ability of robots to move a prescribed (real) distance at each time instant. In this paper, we investigate the SUIG problem for robots operating in a discrete universe (i.e., a graph) where they can only move one unit of distance (i.e., to an adjacent node) at each time instant. Specifically, we focus on line-shaped networks and characterize the solvability of the SUIG problem for oblivious robots without multiplicity detection.

Published
2023

9. Stand Up Indulgent Gathering

Author

Bramas, Quentin, Lamani, Anissa, and Tixeuil, Sébastien

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing, Computer Science - Multiagent Systems
Abstract

We consider a swarm of mobile robots evolving in a bidimensional Euclidean space. We study a variant of the crash-tolerant gathering problem: if no robot crashes, robots have to meet at the same arbitrary location, not known beforehand, in finite time; if one or several robots crash at the same location, the remaining correct robots gather at the crash location to rescue them. Motivated by impossibility results in the semi-synchronous setting, we present the first solution to the problem for the fully synchronous setting that operates in the vanilla Look-Compute-Move model with no additional hypotheses: robots are oblivious, disoriented, have no multiplicity detection capacity, and may start from arbitrary positions (including those with multiplicity points). We furthermore show that robots gather in a time that is proportional to the initial maximum distance between robots., Comment: arXiv admin note: substantial text overlap with arXiv:2010.04400

Published
2023

10. Fault-Tolerant Offline Multi-Agent Path Planning

Author

Okumura, Keisuke and Tixeuil, Sébastien

Subjects
Computer Science - Robotics, Computer Science - Artificial Intelligence, Computer Science - Multiagent Systems
Abstract

We study a novel graph path planning problem for multiple agents that may crash at runtime, and block part of the workspace. In our setting, agents can detect neighboring crashed agents, and change followed paths at runtime. The objective is then to prepare a set of paths and switching rules for each agent, ensuring that all correct agents reach their destinations without collisions or deadlocks, despite unforeseen crashes of other agents. Such planning is attractive to build reliable multi-robot systems. We present problem formalization, theoretical analysis such as computational complexities, and how to solve this offline planning problem., Comment: to be presented at AAAI-23

Published
2022

11. Challenger: Blockchain-based Massively Multiplayer Online Game Architecture

Author

Chan Yip Hon, Boris, Zaghdoudi, Bilel, Potop-Butucaru, Maria, Tixeuil, Sébastien, Fdida, Serge, Goos, Gerhard, Series Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Castañeda, Armando, editor, Enea, Constantin, editor, and Gupta, Nirupam, editor

Published
2024
Full Text
View/download PDF

13. QUANTAS: Quantitative User-friendly Adaptable Networked Things Abstract Simulator

Author

Oglio, Joseph, Hood, Kendric, Nesterenko, Mikhail, and Tixeuil, Sebastien

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

We present QUANTAS: a simulator that enables quantitative performance analysis of distributed algorithms. It has a number of attractive features. QUANTAS is an abstract simulator, therefore, the obtained results are not affected by the specifics of a particular network or operating system architecture. QUANTAS allows distributed algorithms researchers to quickly investigate a potential solution and collect data about its performance. QUANTAS programming is relatively straightforward and is accessible to theoretical researchers. To demonstrate QUANTAS capabilities, we implement and compare the behavior of two representative examples from four major classes of distributed algorithms: blockchains, distributed hash tables, consensus, and reliable data link message transmission.

Published
2022

14. Constrained Backward Time Travel Planning is in P

Author

Bramas, Quentin, Luttringer, Jean-Romain, and Tixeuil, Sébastien

Subjects
Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms
Abstract

We consider transportation networks that are modeled by dynamic graphs, and introduce the possibility for traveling agents to use Backward Time-Travel (BTT) devices at any node to go back in time (to some extent, and with some appropriate fee) before resuming their trip. We focus on dynamic line graphs. In more detail, we propose exact algorithms to compute travel plans with constraints on the BTT cost or on how far back in time you can go, while minimizing travel delay (that is, the time difference between the arrival instant and the starting instant), in polynomial time. We study the impact of the BTT devices pricing policies on the computation process of those plans considering travel delay and cost, and provide necessary properties that pricing policies should satisfy to enable to compute such plans. Finally, we provide an optimal online algorithm for the unconstrained problem when the cost function is the identity.

Published
2022

19. Offline Constrained Backward Time Travel Planning

Author

Bramas, Quentin, Luttringer, Jean-Romain, Tixeuil, Sébastien, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Dolev, Shlomi, editor, and Schieber, Baruch, editor

Published
2023
Full Text
View/download PDF

21. Data-Driven Evaluation of Intrusion Detectors: A Methodological Framework

Author

Ayoubi, Solayman, Blanc, Gregory, Jmila, Houda, Silverston, Thomas, Tixeuil, Sébastien, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Jourdan, Guy-Vincent, editor, Mounier, Laurent, editor, Adams, Carlisle, editor, Sèdes, Florence, editor, and Garcia-Alfaro, Joaquin, editor

Published
2023
Full Text
View/download PDF

26. Quixo is Solved

Author

Tanaka, Satoshi, Bonnet, François, Tixeuil, Sébastien, Tamura, Yasumasa, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Browne, Cameron, editor, Kishimoto, Akihiro, editor, and Schaeffer, Jonathan, editor

Published
2022
Full Text
View/download PDF

29. Reliable Broadcast Despite Mobile Byzantine Faults

Author

Silvia Bonomi and Giovanni Farina and Sébastien Tixeuil, Bonomi, Silvia, Farina, Giovanni, Tixeuil, Sébastien, Silvia Bonomi and Giovanni Farina and Sébastien Tixeuil, Bonomi, Silvia, Farina, Giovanni, and Tixeuil, Sébastien

Abstract

We investigate the solvability of the Byzantine Reliable Broadcast and Byzantine Broadcast Channel problems in distributed systems affected by Mobile Byzantine Faults. We show that both problems are not solvable even in one of the most constrained system models for mobile Byzantine faults defined so far. By endowing processes with an additional local failure oracle, we provide a solution to the Byzantine Broadcast Channel problem.

Published
2024
Full Text
View/download PDF

32. An Asynchronous Maximum Independent Set Algorithm By Myopic Luminous Robots On Grids.

Author

Kamei, Sayaka and Tixeuil, Sébastien

Abstract

We consider the problem of constructing a maximum independent set with mobile myopic luminous robots on a grid network whose size is finite but unknown to the robots. In this setting, the robots enter the grid network one by one from a corner of the grid, and they eventually have to be disseminated on the grid nodes so that the occupied positions form a maximum independent set of the network. We assume that robots are asynchronous, anonymous, silent and they execute the same distributed algorithm. In this paper, we propose two algorithms: The first one assumes that the number of light colors of each robot is three and the visible range is two, but uses the additional assumption that a local edge-labeling exists for each node. To remove this assumption, the second one assumes that the number of light colors of each robot is seven, and that the visible range is three. In both algorithms, the number of movements is |$O(n(L+l))$| steps, where |$n$| is the number of nodes and |$L$| and |$l$| are the grid dimensions. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

33. Rendez-vous avec un lapin

Author

Bramas, Quentin, Lamani, Anissa, Tixeuil, Sébastien, Université de Strasbourg (UNISTRA), Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Equipe Réseaux du laboratoire ICUBE (ICUBE-Réseaux), Département Informatique du laboratoire ICUBE (ICUBE-Informatique), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), Networks and Performance Analysis (NPA), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
tolérance aux pannes, rassemblement, Réseaux de robots, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

International audience; Nous nous intéressons à une version du problème du rassemblement de robots mobiles où certains d'entre eux peuvent poser un lapin aux autres. Étant donné un ensemble de robots mobiles : si aucun des robots ne tombe en panne alors tous les robots doivent se rassembler à la même position, non connue à l'avance, en un temps fini. Si un, ou plusieurs robots tombe(nt) en panne à la même position (et posent donc un lapin aux autres), alors tous les autres robots encore en fonction doivent se rassembler à la même position que ceux qui sont en panne. Motivés par les résultats d'impossibilité dans le cadre semi-synchrone, nous présentons dans ce papier, le premier algorithme résolvant le problème dans un environnement synchrone, en supposant le modèle vision-calcul-déplacement, sans hypothèses supplémentaires : les robots sont amnésiques, désorientés, ne peuvent pas détecter de multiplicité, et peuvent commencer leur exécution à n'importe quelle position (y compris celles avec des points de multiplicité).

Published
2023

34. Realistic Self-Stabilization (Invited Talk)

Author

Sébastien Tixeuil, Tixeuil, Sébastien, Sébastien Tixeuil, and Tixeuil, Sébastien

Abstract

It is almost fifty years since Dijkstra coined the term "self-stabilization" to denote a distributed system able to recover correct behavior starting from any arbitrary (even unreachable) configuration. His seminal paper triggered many works since then, exploring over the years new variants of the original concept, new application domains, and new complexity results. While the huge majority of those contributions relates to theory, considering computability and worst case complexity issues, this talk revisits old and recent contributions from the prism of "realistic" distributed systems, aiming to address the following question: is self-stabilization relevant in practice for distributed systems?

Published
2023
Full Text
View/download PDF

35. Semi‐uniform deployment of mobile robots in perfect ℓ$$ \ell $$‐ary trees.

Author

Shibata, Masahiro and Tixeuil, Sébastien

Subjects
MOBILE robots, PROBLEM solving, TREES, VISIBLE spectra, ROBOTS
Abstract

Summary: In this paper, we consider the problem of semi‐uniform deployment for mobile robots in perfect ℓ$$ \ell $$‐ary trees. This problem requires robots to spread in the tree so that, for some positive integer d$$ d $$ and some fixed integer s(0≤s≤d−1)$$ s\left(0\le s\le d-1\right) $$, each node of depth s+dj(j≥0)$$ s+ dj\left(j\ge 0\right) $$ is occupied by a robot. Robots have an infinite visibility range but are opaque, and each robot can emit a light color visible to itself and other robots, taken from a set of κ$$ \kappa $$ colors, at each time step. Then, we clarify the solvability of the semi‐uniform deployment problem, focusing on the number of available light colors. First, we consider robots with κ=1$$ \kappa =1 $$. In this setting, we show that there is no collision‐free algorithm to solve the problem. Next, relax the number of available light colors, that is, we consider robots with κ=2$$ \kappa =2 $$. In this setting, we propose a collision‐free algorithm that can solve the problem. From these results, we can show that the semi‐uniform deployment problem can be solved when κ≥2$$ \kappa \ge 2 $$, and our proposed algorithm is optimal with respect to the number of used light colors (i.e., 2). [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

39. Realistic Self-Stabilization (Invited Talk)

Author

Tixeuil, Sébastien

Subjects
Computing methodologies → Distributed algorithms, Theory of computation → Distributed computing models, Networks → Mobile networks, Performance evaluation, Probable stabilization, Computer systems organization → Dependable and fault-tolerant systems and networks, Asynchronous message passing, Multi-tolerance, Theory of computation → Distributed algorithms, Security and privacy → Distributed systems security, Distributed systems, Self-stabilization
Abstract

It is almost fifty years since Dijkstra coined the term "self-stabilization" to denote a distributed system able to recover correct behavior starting from any arbitrary (even unreachable) configuration. His seminal paper triggered many works since then, exploring over the years new variants of the original concept, new application domains, and new complexity results. While the huge majority of those contributions relates to theory, considering computability and worst case complexity issues, this talk revisits old and recent contributions from the prism of "realistic" distributed systems, aiming to address the following question: is self-stabilization relevant in practice for distributed systems?, LIPIcs, Vol. 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022), pages 3:1-3:1

Published
2023
Full Text
View/download PDF

40. Semi-Uniform Deployment of Mobile Robots in Perfect ℓ-ary Trees

Author

Shibata, Masahiro and Tixeuil, Sébastien

Subjects
Computer Science::Robotics, semi-uniform deployment, visible lights, mobile robot
Abstract

In this paper, we consider the problem of semi-uniform deployment for mobile robots in perfect ℓ-ary trees, where every intermediate node has ℓ children, and all leaf nodes have the same depth. This problem requires robots to spread in the tree so that, for some positive integer d and some fixed integer s(0≤s≤d−1), each node of depth s+dj (j≥0) is occupied by a robot. In other words, after semi-uniform deployment is achieved, nodes of depth s,s+d,s+2d,… are occupied by a robot. Robots have an infinite visibility range but are opaque, that is, robot ri cannot observe some robot rj if there exists another robot rk in the path between ri and rj. In addition, each robot can emit a light color visible to itself and other robots, taken from a set of κ colors, at each time step. Then, we clarify the relationship between the number of available light colors and the solvability of the semi-uniform deployment problem. First, we consider robots with the minimum number of available light colors, that is, robots with κ=1 (in this case, robots are oblivious). In this setting, we show that there is no collision-free algorithm to solve the semi-uniform deployment problem with explicit termination. Next, we relax the number of available light colors, that is, we consider robots with κ=2. In this setting, we propose a collision-free algorithm that can solve the problem with explicit termination. Thus, our algorithm is optimal with respect to the number of light colors. In addition, to the best of our knowledge, this paper is the first to report research considering (a variant of) uniform deployment in graphs other than rings or grids., 2021 Ninth International Symposium on Computing and Networking, CANDAR 2021, 23-26 November, 2021, Virtual Conference

Published
2021

41. Realistic Self-stabilization

Author

Tixeuil, Sébastien, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU)

Subjects
distributed systems, safety, self-stabilization, [INFO]Computer Science [cs], performance, fault-tolerance
Abstract

International audience; It is almost fifty years since Dijkstra coined the term "self-stabilization" to denote a distributed system able to recover correct behavior starting from any arbitrary (even unreachable) configuration. His seminal paper triggered many works since then, exploring over the years new variants of the original concept, new application domains, and new complexity results. While the huge majority of those contributions relates to theory, considering computability and worst case complexity issues, this talk revisits old and recent contributions from the prism of ``realistic'' distributed systems, aiming to address the following question: is self-stabilization relevant in practice for distributed systems?

Published
2022

42. Asynchronous Gathering in a Torus

Author

Kamei, Sayaka, Lamani, Anissa, Ooshita, Fukuhito, Tixeuil, Sébastien, Wada, Koichi, Tixeuil, Sébastien, Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps - - ESTATE2016 - ANR-16-CE25-0009 - AAPG2016 - VALID, Sûreté et preuve de protocoles adaptatifs pour robots oublieux - - SAPPORO2019 - ANR-19-CE25-0005 - AAPG2019 - VALID, Graduate School of Advanced Science and Engineering [Higashi-Hiroshima], Hiroshima University, Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Nara Institute of Science and Technology - Graduate School of Information Science (NAIST), Nara Institute of Science and Technology, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Faculty of Science and Engineering, Hosei University, Hosei University, ANR-16-CE25-0009,ESTATE,Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps(2016), ANR-19-CE25-0005,SAPPORO,Sûreté et preuve de protocoles adaptatifs pour robots oublieux(2019), Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Réseau nanophotonique et optique, Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Matériaux et nanosciences d'Alsace (FMNGE), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), and Hosei University [Chiyoda]

Subjects
FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Theory of computation ��� Distributed algorithms, Robots gathering, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-RB] Computer Science [cs]/Robotics [cs.RO], Autonomous distributed systems, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Torus, Computer Science::Robotics, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Computer Science - Distributed, Parallel, and Cluster Computing, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Distributed algorithms, [INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO], [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract

We consider the gathering problem for asynchronous and oblivious robots that cannot communicate explicitly with each other, but are endowed with visibility sensors that allow them to see the positions of the other robots. Most of the investigations on the gathering problem on the discrete universe are done on ring shaped networks due to the number of symmetric configuration. We extend in this paper the study of the gathering problem on torus shaped networks assuming robots endowed with local weak multiplicity detection. That is, robots cannot make the difference between nodes occupied by only one robot from those occupied by more than one robots unless it is their current node. As a consequence, solutions based on creating a single multiplicity node as a landmark for the gathering cannot be used. We present in this paper a deterministic algorithm that solves the gathering problem starting from any rigid configuration on an asymmetric unoriented torus shaped network., Comment: 41 pages

Published
2022
Full Text
View/download PDF

43. Qui ne se ressemble pas s'assemble

Author

Bramas, Quentin, Lamani, Anissa, Tixeuil, Sébastien, Université de Strasbourg (UNISTRA), Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Equipe Réseaux du laboratoire ICUBE (ICUBE-Réseaux), Département Informatique du laboratoire ICUBE (ICUBE-Informatique), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), ANR-19-CE25-0005,SAPPORO,Sûreté et preuve de protocoles adaptatifs pour robots oublieux(2019), ANR-16-CE25-0009,ESTATE,Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps(2016), Bramas, Quentin, Sûreté et preuve de protocoles adaptatifs pour robots oublieux - - SAPPORO2019 - ANR-19-CE25-0005 - AAPG2019 - VALID, and Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps - - ESTATE2016 - ANR-16-CE25-0009 - AAPG2016 - VALID

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF], [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-PF] Computer Science [cs]/Performance [cs.PF], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Abstract

International audience; Nous nous intéressons au problème du rendezvous de deux robots autonomes à capacités réduites. Il a été démontré dans la littérature que le problème n'admet pas de solution déterministe dans le modèle semi-synchrone si les robots sont amnésiques et que leur système de coordonnées est symétrique. Dans cet article, nous montrons qu'il suffit que les robots admettent des unités de distance différentes pour que le problème devienne soluble. Mots-clefs : Réseaux de robots, rassemblement, désaccord † Ce travail a été financé en partie par le projet ANR project SAPPORO, ref. 2019-CE25-0005-1 et par le projet ANR ESTATE, ref. ANR-16-CE25-0009-03.

Published
2022

44. Il était une fois Algotel

Author

Mathieu, Fabien, Tixeuil, Sébastien, Laboratory of Information, Network and Communication Sciences (LINCS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT), Swapcard, Networks and Performance Analysis (NPA), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-TT]Computer Science [cs]/Document and Text Processing, Domaine scientifique, Bibliométrie, Communauté, Algotel
Abstract

International audience; Les notions de « communauté scientifique » et de « domaine de recherche » sont des éléments centraux pour les chercheurs et les articles qu'ils publient. Nous proposons d'explorer l'évolution de la communauté Algotel depuis sa création à partir des articles recensés dans DBLP et des comités de programme. Nos résultats permettent d'une part de mieux comprendre l'évolution de la communauté, et d'autre part d'intégrer facilement de nouvelles thématiques ou chercheurs lors des éditions futures.

Published
2022

45. Swarms of Mobile Robots: Towards Versatility with Safety

Author

Pierre Courtieu and Lionel Rieg and Sébastien Tixeuil and Xavier Urbain, Courtieu, Pierre, Rieg, Lionel, Tixeuil, Sébastien, Urbain, Xavier, Pierre Courtieu and Lionel Rieg and Sébastien Tixeuil and Xavier Urbain, Courtieu, Pierre, Rieg, Lionel, Tixeuil, Sébastien, and Urbain, Xavier

Abstract

We present Pactole, a formal framework to design and prove the correctness of protocols (or the impossibility of their existence) that target mobile robotic swarms. Unlike previous approaches, our methodology unifies in a single formalism the execution model, the problem specification, the protocol, and its proof of correctness. The Pactole framework makes use of the Coq proof assistant, and is specially targeted at protocol designers and problem specifiers, so that a common unambiguous language is used from the very early stages of protocol development. We stress the underlying framework design principles to enable high expressivity and modularity, and provide concrete examples about how the Pactole framework can be used to tackle actual problems, some previously addressed by the Distributed Computing community, but also new problems, while being certified correct.

Published
2022
Full Text
View/download PDF

46. Comment réduire efficacement l'entropie des sources malveillantes d'information

Author

Bonomi, Silvia (author), Decouchant, Jérémie (author), Farina, Giovanni (author), Rahli, Vincent (author), Tixeuil, Sébastien (author), Bonomi, Silvia (author), Decouchant, Jérémie (author), Farina, Giovanni (author), Rahli, Vincent (author), and Tixeuil, Sébastien (author)

Abstract

Nous considérons un réseau (modélisé par un graphe) utilisé pour propager des informations. Dans ce contexte, une source d’information diffuse à l’ensemble du réseau un message. Si la source est fiable, c’est à dire qu’elle envoie le même message à tous ses voisins directs, on souhaite qu’un nombre limité de participants malveillants qui tentent de miner sa crédibilité en retransmettant des messages sourcés contradictoires, ne puisse pas berner les participants hon- nêtes. Si la source est malveillante (et qu’elle cherche à augmenter l’entropie en envoyant tout et son contraire à ses voisins directs), les participants honnêtes doivent diminuer l’entropie des messages issus de la source, soit en les igno- rant, soit en délivrant un unique message (le même pour tous). Dans cet article, nous montrons que les méthodes dans la littérature pour résoudre ce problème peuvent être améliorées grâce à des optimisations spécifiques et inter-couches. Nos simulations montrent que ces optimisations peuvent être efficacement combinées pour diminuer la quantité totale d’informations transmises ou la latence du protocole., Dataintensive Systems

Published
2022

47. Fun with FUN

Author

Fabien Mathieu and Sébastien Tixeuil, Mathieu, Fabien, Tixeuil, Sébastien, Fabien Mathieu and Sébastien Tixeuil, Mathieu, Fabien, and Tixeuil, Sébastien

Abstract

The notions of scientific community and research field are central elements for researchers and the articles they publish. We propose to explore the evolution of the FUN conference community since its creation from the articles listed in DBLP, authors, program committees, and advertised themes, by means of a novel symmetric embedding, and carefully crafted software tools. Our results make it possible on the one hand to better understand the evolution of the community, and on the other hand to easily integrate new themes or researchers during future editions.

Published
2022
Full Text
View/download PDF

48. Asynchronous Gathering in a Torus

Author

Sayaka Kamei and Anissa Lamani and Fukuhito Ooshita and Sébastien Tixeuil and Koichi Wada, Kamei, Sayaka, Lamani, Anissa, Ooshita, Fukuhito, Tixeuil, Sébastien, Wada, Koichi, Sayaka Kamei and Anissa Lamani and Fukuhito Ooshita and Sébastien Tixeuil and Koichi Wada, Kamei, Sayaka, Lamani, Anissa, Ooshita, Fukuhito, Tixeuil, Sébastien, and Wada, Koichi

Abstract

We consider the gathering problem for asynchronous and oblivious robots that cannot communicate explicitly with each other but are endowed with visibility sensors that allow them to see the positions of the other robots. Most investigations on the gathering problem on the discrete universe are done on ring shaped networks due to the number of symmetric configurations. We extend in this paper the study of the gathering problem on torus shaped networks assuming robots endowed with local weak multiplicity detection. That is, robots cannot make the difference between nodes occupied by only one robot from those occupied by more than one robot unless it is their current node. Consequently, solutions based on creating a single multiplicity node as a landmark for the gathering cannot be used. We present in this paper a deterministic algorithm that solves the gathering problem starting from any rigid configuration on an asymmetric unoriented torus shaped network.

Published
2022
Full Text
View/download PDF

49. Time Reversal Precoding with Artificial Noise Injection for Physical Layer Security

Author

De Doncker, Philippe, Sarrazin, Julien S. J., Tixeuil, Sébastien, Horlin, François, Rottenberg, Francois, Wigger, Michèle, Louveaux, Jerome, Sarkiss, Mireille, Golstein, Sidney, De Doncker, Philippe, Sarrazin, Julien S. J., Tixeuil, Sébastien, Horlin, François, Rottenberg, Francois, Wigger, Michèle, Louveaux, Jerome, Sarkiss, Mireille, and Golstein, Sidney

Abstract

An increasing number of devices exchanges data via the wireless medium into large scale, decentralized, and heterogeneous networks, leading to the concept of Internet of Things (IoT). This PhD work proposes a new practical scheme to perform physical layer security (PLS) in this IoT context.Wireless communications in IoT networks are prone to passive eavesdropping. Therefore, this work introduces a scheme that guarantees the reliability of a communication from a transmitter (Alice) towards a legitimate user (Bob), while preventing multiple passive eavesdroppers (Eve) to correctly decode the data in a worst-cases scenario, thereby considering i) Eve to be noiseless, ii) Eve equipped with an arbitrarily large number of antennas, iii) Alice imperfectly estimating Bob's channel state information (CSI). To do so, a frequency domain time-reversal (TR) precoder is proposed using orthogonal frequency-division multiplexing (OFDM) and artificial noise (AN) injection. The scheme exploits the frequency diversity selective behaviour in multipath channels, and can be incorporated into existing standards, such as in LTE or 5G networks. Different configurations are investigated, namely, single-input single-output (SISO), multiple-input single-output (MISO), and single-input multiple-output (SIMO) systems.The handshake procedures between Alice and Bob are described, both in time-division duplexing (TDD) and frequency-division duplexing (FDD) systems, highlighting the amount of CSI acquisition at Eve, which influences the secrecy performances. Depending on the handshake procedures, different decoding structures are investigated at Eve for each system configuration, considering a block-fading environment. Closed-form approximations of the signal-to-noise ratio required at Bob and the maximal CSI error that can be made at Alice, in order to guarantee a communication ergodic secrecy rate (ESR), are derived. Furthermore, the optimal amount of AN energy to inject, as well as the maximal nu, Doctorat en Sciences de l'ingénieur et technologie, info:eu-repo/semantics/nonPublished

Published
2022

50. Fun with FUN

Author

Mathieu, Fabien, Tixeuil, Sébastien, Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), Networks and Performance Analysis (NPA), LIP6, and Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-TT]Computer Science [cs]/Document and Text Processing, 2012 ACM Subject Classification Information systems → Similarity measures, Information systems → Similarity measures, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Relevance Propagation, Bibliometry, Information systems → Information extraction phrases Natural Language Processing, Scientific Fields, Information systems → Information extraction, Community, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Natural Language Processing
Abstract

The notions of scientific community and research field are central elements for researchers and the articles they publish. We propose to explore the evolution of the FUN conference community since its creation from the articles listed in DBLP, authors, program committees, and advertised themes, by means of a novel symmetric embedding, and carefully crafted software tools. Our results make it possible on the one hand to better understand the evolution of the community, and on the other hand to easily integrate new themes or researchers during future editions., LIPIcs, Vol. 226, 11th International Conference on Fun with Algorithms (FUN 2022), pages 21:1-21:13

Published
2022
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results