Papers by Sebastien Tixeuil
Theoretical Computer Science, Mar 17, 2010
This paper considers gossiping among mobile agents in graphs: agents move on the graph and have t... more This paper considers gossiping among mobile agents in graphs: agents move on the graph and have to disseminate their initial information to every other agent. We focus on self-stabilizing solutions for the gossip problem, where agents may start from arbitrary locations in arbitrary states. Self-stabilization requires (some of the) participating agents to keep moving forever, hinting at maximizing the number of agents that could be allowed to stop moving eventually. This paper formalizes the self-stabilizing agent gossip problem, ...
Bookmarks Related papers MentionsView impact
implementation is: \emph{message efficient} if all but finitely many messages are sent by a singl... more implementation is: \emph{message efficient} if all but finitely many messages are sent by a single process; \emph{packet efficient} if the number of packets used to transmit a message in all but finitely many messages is linear w.r.t the number of processes, packets of different messages may potentially use different channels, thus the number of used channels is not limited; \emph{super packet efficient} if the number of channels used by packets to transmit all but finitely many messages is linear.We present the following results for deterministic algorithms. If reliability and timeliness of one message does not correlate with another, i.e., there are no channel reliability properties, then a packet efficient implementation of Omega is impossible. If eventuallytimely and fair-lossy channels are considered, we establish necessary and sufficient conditions for the existence of a message and packet efficient implementation of Omega. We also prove that the eventuality of timeliness of channels makes a super packet efficientimplementation of Omega impossible. On the constructive side, we present and prove correct a deterministic packet efficient implementation of Omega that matches the necessary conditions we established.
Bookmarks Related papers MentionsView impact
Abstract Wormhole routing is the most common in parallel architecture in which messages are sent ... more Abstract Wormhole routing is the most common in parallel architecture in which messages are sent in small fragments called flits. It is a lightweight and efficient method of routing messages between parallel processors. Self-stabilization is a technique that guarantees tolerance to transient faults (eg memory corruption or communication hazard) for a given protocol. Self-stabilization guarantees that the network recovers to a correct behavior infinite time, without the need for human intervention.
Bookmarks Related papers MentionsView impact
The maximal matching problem has received considerable attention in the self-stabilizing communit... more The maximal matching problem has received considerable attention in the self-stabilizing community. Previous work has given different self-stabilizing algorithms that solves the problem for both the adversarial and fair distributed daemon, the sequential adversarial daemon, as well as the synchronous daemon.
Bookmarks Related papers MentionsView impact
Abstract Self-stabilization is a strong property which guarantees that a network always resume a ... more Abstract Self-stabilization is a strong property which guarantees that a network always resume a correct behavior starting from an arbitrary initial state. Weaker guarantees have later been introduced to cope with impossibility results: probabilistic stabilization only gives probabilistic convergence to a correct behavior. Also, weak-stabilization only gives the possibility of convergence. In this paper, we investigate the relative power of weak, self, and probabilistic stabilization, with respect to the set of problems that can be solved.
Bookmarks Related papers MentionsView impact
Page 1. Parallel Processing Letters Vol. 12' Nos. 3 & 4 (2002) 327-340 c World Scientific Publish... more Page 1. Parallel Processing Letters Vol. 12' Nos. 3 & 4 (2002) 327-340 c World Scientific Publishing Company OPT1MAL SNAP-STAB1L1Z1NG NE1GHBOROOD SYNCHRON1ZER 1N TREE NETWORKS£ COLETTE JOHNEN LRI - CNRS UMR 8623, Universite Paris-Sud France LUC O. ALIMA Unite d'Informatique, Universite Catholique de Louvain Belgium AJOY K.
Bookmarks Related papers MentionsView impact
Abstract In a network consisting of several thousands computers, the occurrence of faults is unav... more Abstract In a network consisting of several thousands computers, the occurrence of faults is unavoidable. Being able to test the behavior of a distributed program in an environment where we can control the faults (such as the crash of a process) is an important feature that matters in the deployment of reliable programs.
Bookmarks Related papers MentionsView impact
Abstract. We consider a team of k identical, oblivious, semi-synchronous mobile robots that are a... more Abstract. We consider a team of k identical, oblivious, semi-synchronous mobile robots that are able to sense (ie, view) their environment, yet are unable to communicate, and evolve on a constrained path. Previous results in this weak scenario show that initial symmetry yields high lower bounds when problems are to be solved by deterministic robots. In this paper, we initiate research on probabilistic bounds and solutions in this context, and focus on the exploration problem of anonymous unoriented rings of any size.
Bookmarks Related papers MentionsView impact
We consider a set of k autonomous robots that are endowed with visibility sensors (but that are o... more We consider a set of k autonomous robots that are endowed with visibility sensors (but that are otherwise unable to communicate) and motion actuators. Those robots must collaborate to reach a single vertex that is unknown beforehand, and to remain there hereafter.
Bookmarks Related papers MentionsView impact
Self-stabilizing systems have the ability to converge to a correct behavior when started in any c... more Self-stabilizing systems have the ability to converge to a correct behavior when started in any configuration. Most of the work done so far in the self-stabilization area assumed either communication via shared memory or via FIFO channels. This paper is the first to lay the bases for the design of self-stabilizing message passing algorithms over unreliable non-FIFO channels.
Bookmarks Related papers MentionsView impact
Abstract: We survey existing scheduling hypotheses made in the literature in self-stabilization, ... more Abstract: We survey existing scheduling hypotheses made in the literature in self-stabilization, commonly referred to under the notion of daemon. We show that four main characteristics (distribution, fairness, boundedness, and enabledness) are enough to encapsulate the various differences presented in existing work. Our naming scheme makes it easy to compare daemons of particular classes, and to extend existing possibility or impossibility results to new daemons.
Bookmarks Related papers MentionsView impact
Self-stabilization is a versatile technique to withstand any transient fault in a distributed sys... more Self-stabilization is a versatile technique to withstand any transient fault in a distributed system. Mobile robots (or agents) are one of the emerging trends in distributed computing as they mimic autonomous biologic entities. The contribution of this paper is threefold. First, we present a new model for studying mobile entities in networks subject to transient faults.
Bookmarks Related papers MentionsView impact
Abstract: Modern networks assemble an ever growing number of nodes. However, it remains difficult... more Abstract: Modern networks assemble an ever growing number of nodes. However, it remains difficult to increase the number of channels per node, thus the maximal degree of the network may be bounded. This is typically the case in grid topology networks, where each node has at most four neighbors. In this paper, we address the following issue: if each node is likely to fail in an unpredictable manner, how can we preserve some global reliability guarantees when the number of nodes keeps increasing unboundedly?
Bookmarks Related papers MentionsView impact
Abstract: In this paper, we propose optimal (wrt, the number of robots) solutions for the determi... more Abstract: In this paper, we propose optimal (wrt, the number of robots) solutions for the deterministic exploration of a grid shaped network by a team of k asynchronous oblivious robots. In more details, we first show that no exploration protocol exists with less than three robots for any grid with more than three nodes, less than four robots for the (2, 2)-Grid, and less than five robots for the (3, 3)-Grid. Next, we show that the problem is solvable using only 3 robots for any (i, j)-Grid, provided that j> 3.
Bookmarks Related papers MentionsView impact
Abstract: A self-stabilizing simulation of a single-writer multi-reader atomic register is presen... more Abstract: A self-stabilizing simulation of a single-writer multi-reader atomic register is presented. The simulation works in asynchronous message-passing systems, and allows processes to crash, as long as at least a majority of them remain working. A key element in the simulation is a new combinatorial construction of a bounded labeling scheme that can accommodate arbitrary labels, ie, including those not generated by the scheme itself.
Bookmarks Related papers MentionsView impact
Abstract Self-stabilization is a versatile approach to fault-tolerance since it permits a distrib... more Abstract Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors. Combining these two properties proved difficult: it is impossible to contain the spatial impact of Byzantine nodes in a self-stabilizing context for global tasks such as tree orientation and tree construction.
Bookmarks Related papers MentionsView impact
Abstract A self-stabilizing algorithm, regardless of the initial system state, converges in finit... more Abstract A self-stabilizing algorithm, regardless of the initial system state, converges in finite time to a set of states that satisfy a legitimacy predicate. The mutual exclusion problem is fundamental in distributed computing, since it allows processors competing to access a shared resource to be able to synchronize and get exclusive access to the resource (ie execute their critical section).
Bookmarks Related papers MentionsView impact
Nous abordons le probleme de la stabilisation instantanée dans les systemes répartisa passage de ... more Nous abordons le probleme de la stabilisation instantanée dans les systemes répartisa passage de messages. Notre contribution est double. Tout d'abord, nous montrons que la stabilisation instantanée est impossible pour la plupart des problemes dans de tels systemes si nous supposons que la capacité des canaux de communication est finie mais non bornée. Nous montrons ensuite que la stabilisation instantanée devient réalisable si nous connaissons une borne sur la capacité des canaux de communication.
Bookmarks Related papers MentionsView impact
Abstract The growth of User-Generated Content (UGC) traffic makes the understanding of its nature... more Abstract The growth of User-Generated Content (UGC) traffic makes the understanding of its nature a priority for network operators, content providers and equipment suppliers. In this paper, we study a four-month dataset that logs all video requests to DailyMotion made by a fixed subset of users. We were able to infer user sessions from raw data, to propose a Markovian model of these sessions, and to study video popularity and its evolution over time.
Bookmarks Related papers MentionsView impact
Resumo. O consenso é um problema fundamental para o desenvolvimento de soluções confiáveis em sis... more Resumo. O consenso é um problema fundamental para o desenvolvimento de soluções confiáveis em sistemas distribuídos dinâmicos, tais como sistemas P2P, grades oportunistas, redes móveis ad-hoc, etc. Diferentemente dos sistemas clássicos, onde o conjunto de participantes e suas identidades são conhecidos, nos sistemas dinâmicos não se sabe a priori quais são os pares com quem se pode colaborar, nem quantos deles estão disponíveis.
Bookmarks Related papers MentionsView impact
Uploads
Papers by Sebastien Tixeuil