-
Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs
Authors:
Arnaud Casteigts,
Nils Morawietz,
Petra Wolf
Abstract:
A temporal graph is a graph whose edges only appear at certain points in time. Reachability in these graphs is defined in terms of paths that traverse the edges in chronological order (temporal paths). This form of reachability is neither symmetric nor transitive, the latter having important consequences on the computational complexity of even basic questions, such as computing temporal connected…
▽ More
A temporal graph is a graph whose edges only appear at certain points in time. Reachability in these graphs is defined in terms of paths that traverse the edges in chronological order (temporal paths). This form of reachability is neither symmetric nor transitive, the latter having important consequences on the computational complexity of even basic questions, such as computing temporal connected components. In this paper, we introduce several parameters that capture how far a temporal graph $\mathcal{G}$ is from being transitive, namely, \emph{vertex-deletion distance to transitivity} and \emph{arc-modification distance to transitivity}, both being applied to the reachability graph of $\mathcal{G}$. We illustrate the impact of these parameters on the temporal connected component problem, obtaining several tractability results in terms of fixed-parameter tractability and polynomial kernels. Significantly, these results are obtained without restrictions of the underlying graph, the snapshots, or the lifetime of the input graph. As such, our results isolate the impact of non-transitivity and confirm the key role that it plays in the hardness of temporal graph problems.
△ Less
Submitted 27 June, 2024;
originally announced June 2024.
-
Freeze-Tag in $L_1$ has Wake-up Time Five
Authors:
Nicolas Bonichon,
Arnaud Casteigts,
Cyril Gavoille,
Nicolas Hanusse
Abstract:
The Freeze-Tag Problem, introduced in Arkin et al. (SODA'02) consists of waking up a swarm of $n$ robots, starting from a single active robot. In the basic geometric version, every robot is given coordinates in the plane. As soon as a robot is awakened, it can move towards inactive robots to wake them up. The goal is to minimize the wake-up time of the last robot, the makespan.
Despite significa…
▽ More
The Freeze-Tag Problem, introduced in Arkin et al. (SODA'02) consists of waking up a swarm of $n$ robots, starting from a single active robot. In the basic geometric version, every robot is given coordinates in the plane. As soon as a robot is awakened, it can move towards inactive robots to wake them up. The goal is to minimize the wake-up time of the last robot, the makespan.
Despite significant progress on the computational complexity of this problem and on approximation algorithms, the characterization of exact bounds on the makespan remains one of the main open questions. In this paper, we settle this question for the $\ell_1$-norm, showing that a makespan of at most $5r$ can always be achieved, where $r$ is the maximum distance between the initial active robot and any sleeping robot. Moreover, a schedule achieving a makespan of at most $5r$ can be computed in optimal time $O(n)$. Both bounds, the time and the makespan are optimal. This implies a new upper bound of $5\sqrt{2}r \approx 7.07r$ on the makespan in the $\ell_2$-norm, improving the best known bound so far $(5+2\sqrt{2}+\sqrt{5})r \approx 10.06r$.
△ Less
Submitted 5 February, 2024;
originally announced February 2024.
-
In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs
Authors:
Arnaud Casteigts,
Timothée Corsini
Abstract:
A graph whose edges only appear at certain points in time is called a temporal graph (among other names). These graphs are temporally connected if all ordered pairs of vertices are connected by a path that traverses edges in chronological order (a temporal path). Reachability in temporal graphs departs significantly from standard reachability; in particular, it is not transitive, with structural a…
▽ More
A graph whose edges only appear at certain points in time is called a temporal graph (among other names). These graphs are temporally connected if all ordered pairs of vertices are connected by a path that traverses edges in chronological order (a temporal path). Reachability in temporal graphs departs significantly from standard reachability; in particular, it is not transitive, with structural and algorithmic consequences. For instance, temporally connected graphs do not always admit spanning trees, i.e., subsets of edges that form a tree and preserve temporal connectivity among the nodes.
In this paper, we revisit fundamental questions about the loss of universality of spanning trees. To start, we show that deciding if a spanning tree exists in a given temporal graph is NP-complete. What could be appropriate replacement for the concept? Beyond having minimum size, spanning trees enjoy the feature of enabling reachability along the same underlying paths in both directions, a pretty uncommon feature in temporal graphs. We explore relaxations in this direction and show that testing the existence of bidirectional spanning structures (bi-spanners) is tractable in general. On the down side, finding \emph{minimum} such structures is NP-hard even in simple temporal graphs. Still, the fact that bidirectionality can be tested efficiently may find applications, e.g. for routing and security, and the corresponding primitive that we introduce in the algorithm may be of independent interest.
△ Less
Submitted 11 December, 2023;
originally announced December 2023.
-
Simple, strict, proper, happy: A study of reachability in temporal graphs
Authors:
Arnaud Casteigts,
Timothée Corsini,
Writika Sarkar
Abstract:
Dynamic networks are a complex subject. Not only do they inherit the complexity of static networks (as a particular case); they are also sensitive to definitional subtleties that are a frequent source of confusion and incomparability of results in the literature.
In this paper, we take a step back and examine three such aspects in more details, exploring their impact in a systematic way; namely,…
▽ More
Dynamic networks are a complex subject. Not only do they inherit the complexity of static networks (as a particular case); they are also sensitive to definitional subtleties that are a frequent source of confusion and incomparability of results in the literature.
In this paper, we take a step back and examine three such aspects in more details, exploring their impact in a systematic way; namely, whether the temporal paths are required to be \emph{strict} (i.e., the times along a path must increasing, not just be non-decreasing), whether the time labeling is \emph{proper} (two adjacent edges cannot be present at the same time) and whether the time labeling is \emph{simple} (an edge can have only one presence time). In particular, we investigate how different combinations of these features impact the expressivity of the graph in terms of reachability.
Our results imply a hierarchy of expressivity for the resulting settings, shedding light on the loss of generality that one is making when considering either combination. Some settings are more general than expected; in particular, proper temporal graphs turn out to be as expressive as general temporal graphs where non-strict paths are allowed. Also, we show that the simplest setting, that of \emph{happy} temporal graphs (i.e., both proper and simple) remains expressive enough to emulate the reachability of general temporal graphs in a certain (restricted but useful) sense. Furthermore, this setting is advocated as a target of choice for proving negative results. We illustrates this by strengthening two known results to happy graphs (namely, the inexistence of sparse spanners, and the hardness of computing temporal components). Overall, we hope that this article can be seen as a guide for choosing between different settings of temporal graphs, while being aware of the way these choices affect generality.
△ Less
Submitted 15 December, 2023; v1 submitted 2 August, 2022;
originally announced August 2022.
-
Giant Components in Random Temporal Graphs
Authors:
Ruben Becker,
Arnaud Casteigts,
Pierluigi Crescenzi,
Bojana Kodric,
Malte Renken,
Michael Raskin,
Viktor Zamaraev
Abstract:
A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erdős-Rényi random graph model. The proposed model is obtained by randomly permuting the edges of an Erdős-Rényi random graph and interpreting this permutation as an ordering of presence times. It was shown that the connectivity th…
▽ More
A temporal graph is a graph whose edges appear only at certain points in time. Recently, the second and the last three authors proposed a natural temporal analog of the Erdős-Rényi random graph model. The proposed model is obtained by randomly permuting the edges of an Erdős-Rényi random graph and interpreting this permutation as an ordering of presence times. It was shown that the connectivity threshold in the Erdős-Rényi model fans out into multiple phase transitions for several distinct notions of reachability in the temporal setting.
In the present paper, we identify a sharp threshold for the emergence of a giant temporally connected component. We show that at $p = \log n/n$ the size of the largest temporally connected component increases from $o(n)$ to~$n-o(n)$. This threshold holds for both open and closed connected components, i.e. components that allow, respectively forbid, their connecting paths to use external nodes.
△ Less
Submitted 17 August, 2023; v1 submitted 30 May, 2022;
originally announced May 2022.
-
A Dynamic Data Structure for Temporal Reachability with Unsorted Contact Insertions
Authors:
Luiz F. Afra Brito,
Marcelo Albertini,
Arnaud Casteigts,
Bruno A. N. Travençolo
Abstract:
Temporal graphs represent interactions between entities over the time. These interactions may be direct (a contact between two nodes at some time instant), or indirect, through sequences of contacts called temporal paths (journeys). Deciding whether an entity can reach another through a journey is useful for various applications in communication networks and epidemiology, among other fields. In th…
▽ More
Temporal graphs represent interactions between entities over the time. These interactions may be direct (a contact between two nodes at some time instant), or indirect, through sequences of contacts called temporal paths (journeys). Deciding whether an entity can reach another through a journey is useful for various applications in communication networks and epidemiology, among other fields. In this paper, we present a data structure which maintains temporal reachability information under the addition of new contacts (i.e., triplets $(u,v,t)$ indicating that node $u$ and node $v$ interacted at time $t$). In contrast to previous works, the contacts can be inserted in arbitrary order -- in particular, non-chronologically -- which corresponds to systems where the information is collected a posteriori (e.g. when trying to reconstruct contamination chains among people). The main component of our data structure is a generalization of transitive closure called timed transitive closure (TTC), which allows us to maintain reachability information relative to all nested time intervals, without storing all these intervals, nor the journeys themselves. TTCs are of independent interest and we study a number of their general properties. Let $n$ be the number of nodes and $τ$ be the number of timestamps in the lifetime of the temporal graph. Our data structure answers reachability queries regarding the existence of a journey from a given node to another within given time interval in time $O(\logτ)$; it has an amortized insertion time of $O(n^2\logτ)$; and it can reconstruct a valid journey that witnesses reachability in time $O(k\logτ)$, where $k<n$ is the maximum number of edges of this journey. Finally, the space complexity of our reachability data structure is $O(n^2τ)$, which remains within the worst-case size of the temporal graph itself.
△ Less
Submitted 30 March, 2021; v1 submitted 8 February, 2021;
originally announced February 2021.
-
Revisiting the Role of Coverings in Anonymous Networks: Spanning Tree Construction and Topology Recognition
Authors:
Arnaud Casteigts,
Yves Métivier,
John Michael Robson
Abstract:
This paper revisits two classical distributed problems in anonymous networks, namely spanning tree construction and topology recognition, from the point of view of graph covering theory. For both problems, we characterize necessary and sufficient conditions on the communication graph in terms of directed symmetric coverings. These characterizations answer along-standing open question posed by Yama…
▽ More
This paper revisits two classical distributed problems in anonymous networks, namely spanning tree construction and topology recognition, from the point of view of graph covering theory. For both problems, we characterize necessary and sufficient conditions on the communication graph in terms of directed symmetric coverings. These characterizations answer along-standing open question posed by Yamashita and Kameda [YK96], and shed new light on the connection between coverings and the concepts of views and quotient graphs developed by the same authors. Characterizing conditions in terms of coverings is significant because it connects the field with a vast body of classical literature in graph theory and algebraic topology. In particular, it gives access to powerful tools such as Reidemeister's theorem and Mazurkiewicz's algorithm. Combined together, these tools allow us to present elegant proofs of otherwise intricate results, and their constructive nature makes them effectively usable in the algorithms. This paper also gives us the opportunity to present the field of covering theory in a pedagogical way, with a focus on the two aforementioned tools, whose potential impact goes beyond the specific problems considered in this work.
△ Less
Submitted 23 January, 2021; v1 submitted 5 January, 2021;
originally announced January 2021.
-
Sharp Thresholds in Random Simple Temporal Graphs
Authors:
Arnaud Casteigts,
Michael Raskin,
Malte Renken,
Viktor Zamaraev
Abstract:
A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erdős-Rényi random graph $G~G_{n,p}$ by consid…
▽ More
A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this paper, we consider a simple model of random temporal graph, obtained from an Erdős-Rényi random graph $G~G_{n,p}$ by considering a random permutation $π$ of the edges and interpreting the ranks in $π$ as presence times. Temporal reachability in this model exhibits a surprisingly regular sequence of thresholds. In particular, we show that at $p=\log n/n$ any fixed pair of vertices can a.a.s. reach each other; at $2\log n/n$ at least one vertex (and in fact, any fixed vertex) can a.a.s. reach all others; and at $3\log n/n$ all the vertices can a.a.s. reach each other, i.e., the graph is temporally connected. Furthermore, the graph admits a temporal spanner of size $2n+o(n)$ as soon as it becomes temporally connected, which is nearly optimal as $2n-4$ is a lower bound. This result is significant because temporal graphs do not admit spanners of size $O(n)$ in general (Kempe et al, STOC 2000). In fact, they do not even admit spanners of size $o(n^2)$ (Axiotis et al, ICALP 2016). Thus, our result implies that the obstructions found in these works, and more generally, all non-negligible obstructions, must be statistically insignificant: nearly optimal spanners always exist in random temporal graphs. All the above thresholds are sharp. Carrying the study of temporal spanners further, we show that pivotal spanners -- i.e., spanners of size $2n-2$ made of two spanning trees glued at a single vertex (one descending in time, the other ascending subsequently) -- exist a.a.s. at $4\log n/n$, this threshold being also sharp. Finally, we show that optimal spanners (of size $2n-4$) also exist a.a.s. at $p = 4\log n/n$.
△ Less
Submitted 17 December, 2023; v1 submitted 7 November, 2020;
originally announced November 2020.
-
VectorTSP: A Traveling Salesperson Problem with Racetrack-like acceleration constraints
Authors:
Arnaud Casteigts,
Mathieu Raffinot,
Jason Schoeters
Abstract:
We study a new version of the Euclidean TSP called VectorTSP (VTSP for short) where a mobile entity is allowed to move according to a set of physical constraints inspired from the pen-and-pencil game Racetrack (also known as Vector Racer ). In contrast to other versions of TSP accounting for physical constraints, such as Dubins TSP, the spirit of this model is that (1) no speed limitations apply,…
▽ More
We study a new version of the Euclidean TSP called VectorTSP (VTSP for short) where a mobile entity is allowed to move according to a set of physical constraints inspired from the pen-and-pencil game Racetrack (also known as Vector Racer ). In contrast to other versions of TSP accounting for physical constraints, such as Dubins TSP, the spirit of this model is that (1) no speed limitations apply, and (2) inertia depends on the current velocity. As such, this model is closer to typical models considered in path planning problems, although applied here to the visit of n cities in a non-predetermined order. We motivate and introduce the VectorTSP problem, discussing fundamental differences with previous versions of TSP. In particular, an optimal visit order for ETSP may not be optimal for VTSP. We show that VectorTSP is NP-hard, and in the other direction, that VectorTSP reduces to GroupTSP in polynomial time (although with a significant blow-up in size). On the algorithmic side, we formulate the search for a solution as an interactive scheme between a high-level algorithm and a trajectory oracle, the former being responsible for computing the visit order and the latter for computing the cost (or the trajectory) for a given visit order. We present algorithms for both, and we demonstrate and quantify through experiments that this approach frequently finds a better solution than the optimal trajectory realizing an optimal ETSP tour, which legitimates the problem itself and (we hope) motivates further algorithmic developments.
△ Less
Submitted 20 August, 2021; v1 submitted 5 June, 2020;
originally announced June 2020.
-
The Computational Complexity of Finding Temporal Paths under Waiting Time Constraints
Authors:
Arnaud Casteigts,
Anne-Sophie Himmel,
Hendrik Molter,
Philipp Zschoche
Abstract:
Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps. We investigate a basic constr…
▽ More
Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration $Δ$, referred to as $Δ$-restless temporal paths. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the "restless variant" of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the distance to disjoint path of the underlying graph, which implies W[1]-hardness for many other parameters like feedback vertex number and pathwidth. A natural question is thus whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work.
△ Less
Submitted 26 May, 2021; v1 submitted 13 September, 2019;
originally announced September 2019.
-
Robustness: a New Form of Heredity Motivated by Dynamic Networks
Authors:
Arnaud Casteigts,
Swan Dubois,
Franck Petit,
John M. Robson
Abstract:
We investigate a special case of hereditary property in graphs, referred to as {\em robustness}. A property (or structure) is called robust in a graph $G$ if it is inherited by all the connected spanning subgraphs of $G$. We motivate this definition using two different settings of dynamic networks. The first corresponds to networks of low dynamicity, where some links may be permanently removed so…
▽ More
We investigate a special case of hereditary property in graphs, referred to as {\em robustness}. A property (or structure) is called robust in a graph $G$ if it is inherited by all the connected spanning subgraphs of $G$. We motivate this definition using two different settings of dynamic networks. The first corresponds to networks of low dynamicity, where some links may be permanently removed so long as the network remains connected. The second corresponds to highly-dynamic networks, where communication links appear and disappear arbitrarily often, subject only to the requirement that the entities are temporally connected in a recurrent fashion ({\it i.e.} they can always reach each other through temporal paths). Each context induces a different interpretation of the notion of robustness.
We start by motivating the definition and discussing the two interpretations, after what we consider the notion independently from its interpretation, taking as our focus the robustness of {\em maximal independent sets} (MIS). A graph may or may not admit a robust MIS. We characterize the set of graphs \forallMIS in which {\em all} MISs are robust. Then, we turn our attention to the graphs that {\em admit} a robust MIS (\existsMIS). This class has a more complex structure; we give a partial characterization in terms of elementary graph properties, then a complete characterization by means of a (polynomial time) decision algorithm that accepts if and only if a robust MIS exists. This algorithm can be adapted to construct such a solution if one exists.
△ Less
Submitted 10 May, 2019;
originally announced May 2019.
-
Temporal Cliques Admit Sparse Spanners
Authors:
Arnaud Casteigts,
Joseph G. Peters,
Jason Schoeters
Abstract:
Let $G=(V,E)$ be an undirected graph on $n$ vertices and $λ:E\to 2^{\mathbb{N}}$ a mapping that assigns to every edge a non-empty set of integer labels (times). Such a graph is {\em temporally connected} if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar \cite{KKK02} asked whether, given such a temporal graph, a {\em…
▽ More
Let $G=(V,E)$ be an undirected graph on $n$ vertices and $λ:E\to 2^{\mathbb{N}}$ a mapping that assigns to every edge a non-empty set of integer labels (times). Such a graph is {\em temporally connected} if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar \cite{KKK02} asked whether, given such a temporal graph, a {\em sparse} subset of edges always exists whose labels suffice to preserve temporal connectivity -- a {\em temporal spanner}. Axiotis and Fotakis \cite{AF16} answered negatively by exhibiting a family of $Θ(n^2)$-dense temporal graphs which admit no temporal spanner of density $o(n^2)$. In this paper, we give the first positive answer as to the existence of $o(n^2)$-sparse spanners in a dense class of temporal graphs, by showing (constructively) that if $G$ is a complete graph, then one can always find a temporal spanner of density $O(n \log n)$.
△ Less
Submitted 28 April, 2021; v1 submitted 28 September, 2018;
originally announced October 2018.
-
Finding Structure in Dynamic Networks
Authors:
Arnaud Casteigts
Abstract:
This document is the first part of the author's habilitation thesis (HDR), defended on June 4, 2018 at the University of Bordeaux. Given the nature of this document, the contributions that involve the author have been emphasized; however, these four chapters were specifically written for distribution to a larger audience. We hope they can serve as a broad introduction to the domain of highly dynam…
▽ More
This document is the first part of the author's habilitation thesis (HDR), defended on June 4, 2018 at the University of Bordeaux. Given the nature of this document, the contributions that involve the author have been emphasized; however, these four chapters were specifically written for distribution to a larger audience. We hope they can serve as a broad introduction to the domain of highly dynamic networks, with a focus on temporal graph concepts and their interaction with distributed computing.
△ Less
Submitted 20 July, 2018;
originally announced July 2018.
-
Robustness in Highly Dynamic Networks
Authors:
Arnaud Casteigts,
Swan Dubois,
Franck Petit,
John Michael Robson
Abstract:
We investigate a special case of hereditary property that we refer to as {\em robustness}. A property is {\em robust} in a given graph if it is inherited by all connected spanning subgraphs of this graph. We motivate this definition in different contexts, showing that it plays a central role in highly dynamic networks, although the problem is defined in terms of classical (static) graph theory. In…
▽ More
We investigate a special case of hereditary property that we refer to as {\em robustness}. A property is {\em robust} in a given graph if it is inherited by all connected spanning subgraphs of this graph. We motivate this definition in different contexts, showing that it plays a central role in highly dynamic networks, although the problem is defined in terms of classical (static) graph theory. In this paper, we focus on the robustness of {\em maximal independent sets} (MIS). Following the above definition, a MIS is said to be {\em robust} (RMIS) if it remains a valid MIS in all connected spanning subgraphs of the original graph. We characterize the class of graphs in which {\em all} possible MISs are robust. We show that, in these particular graphs, the problem of finding a robust MIS is {\em local}; that is, we present an RMIS algorithm using only a sublogarithmic number of rounds (in the number of nodes $n$) in the ${\cal LOCAL}$ model. On the negative side, we show that, in general graphs, the problem is not local. Precisely, we prove a $Ω(n)$ lower bound on the number of rounds required for the nodes to decide consistently in some graphs. This result implies a separation between the RMIS problem and the MIS problem in general graphs. It also implies that any strategy in this case is asymptotically (in order) as bad as collecting all the network information at one node and solving the problem in a centralized manner. Motivated by this observation, we present a centralized algorithm that computes a robust MIS in a given graph, if one exists, and rejects otherwise. Significantly, this algorithm requires only a polynomial amount of local computation time, despite the fact that exponentially many MISs and exponentially many connected spanning subgraphs may exist.
△ Less
Submitted 9 March, 2017;
originally announced March 2017.
-
Design Patterns in Beeping Algorithms: Examples, Emulation, and Analysis
Authors:
Arnaud Casteigts,
Yves Métivier,
John Michael Robson,
Akka Zemmari
Abstract:
We consider networks of processes which interact with beeps. In the basic model defined by Cornejo and Kuhn (2010), processes can choose in each round either to beep or to listen. Those who beep are unable to detect simultaneous beeps. Those who listen can only distinguish between silence and the presence of at least one beep. We refer to this model as $BL$ (beep or listen). Stronger models exist…
▽ More
We consider networks of processes which interact with beeps. In the basic model defined by Cornejo and Kuhn (2010), processes can choose in each round either to beep or to listen. Those who beep are unable to detect simultaneous beeps. Those who listen can only distinguish between silence and the presence of at least one beep. We refer to this model as $BL$ (beep or listen). Stronger models exist where the nodes can detect collision while they are beeping ($B_{cd}L$), listening ($BL_{cd}$), or both ($B_{cd}L_{cd}$). Beeping models are weak in essence and even simple tasks are difficult or unfeasible within.
We present a set of generic building blocks (design patterns) which seem to occur frequently in the design of beeping algorithms. They include multi-slot phases: the fact of dividing the main loop into a number of specialised slots; exclusive beeps: having a single node beep at a time in a neighbourhood (within one or two hops); adaptive probability: increasing or decreasing the probability of beeping to produce more exclusive beeps; internal (resp. peripheral) collision detection: for detecting collision while beeping (resp. listening). Based on these patterns, we provide algorithms for a number of basic problems, including colouring, 2-hop colouring, degree computation, 2-hop MIS, and collision detection (in $BL$). The patterns make it possible to formulate these algorithms in a rather concise and elegant way. Their analyses are more technical; one of them improves significantly upon that of the best known MIS algorithm by Jeavons et al. (2016). Finally, inspired by a technique from Afek et al. (2013), our last contribution is to show that any Las Vegas algorithm relying on collision detection can be transposed into a Monte Carlo algorithm without collision detection at the cost of a logarithmic slowdown, which we prove is optimal.
△ Less
Submitted 30 August, 2018; v1 submitted 11 July, 2016;
originally announced July 2016.
-
Counting in One-Hop Beeping Networks
Authors:
A. Casteigts,
Y. Métivier,
J. M. Robson,
A. Zemmari
Abstract:
We consider networks of processes which interact with beeps. In the basic model defined by Cornejo and Kuhn, which we refer to as the $BL$ variant, processes can choose in each round either to beep or to listen. Those who beep are unable to detect simultaneous beeps. Those who listen can only distinguish between silence and the presence of at least one beep. Beeping models are weak in essence and…
▽ More
We consider networks of processes which interact with beeps. In the basic model defined by Cornejo and Kuhn, which we refer to as the $BL$ variant, processes can choose in each round either to beep or to listen. Those who beep are unable to detect simultaneous beeps. Those who listen can only distinguish between silence and the presence of at least one beep. Beeping models are weak in essence and even simple tasks may become difficult or unfeasible with them.
In this paper, we address the problem of computing how many participants there are in a one-hop network: the {\em counting} problem. We first observe that no algorithm can compute this number with certainty in $BL$, whether the algorithm be deterministic or even randomised (Las Vegas). We thus consider the stronger variant where beeping nodes are able to detect simultaneous beeps, referred to as $B_{cd}L$ (for {\em collision detection}). We prove that at least $n$ rounds are necessary in $B_{cd}L$, and we present an algorithm whose running time is $O(n)$ rounds with high probability. Further experimental results show that its expected running time is less than $10n$. Finally, we discuss how this algorithm can be adapted in other beeping models. In particular, we show that it can be emulated in $BL$, at the cost of a logarithmic slowdown and of trading its Las Vegas nature (result certain, time uncertain) against Monte Carlo (time certain, result uncertain).
△ Less
Submitted 31 May, 2016;
originally announced May 2016.
-
Deterministic Leader Election Takes $Θ(D + \log n)$ Bit Rounds
Authors:
Arnaud Casteigts,
Yves Métivier,
John Michael Robson,
Akka Zemmari
Abstract:
Leader election is, together with consensus, one of the most central problems in distributed computing. This paper presents a distributed algorithm, called \STT, for electing deterministically a leader in an arbitrary network, assuming processors have unique identifiers of size $O(\log n)$, where $n$ is the number of processors. It elects a leader in $O(D +\log n)$ rounds, where $D$ is the diamete…
▽ More
Leader election is, together with consensus, one of the most central problems in distributed computing. This paper presents a distributed algorithm, called \STT, for electing deterministically a leader in an arbitrary network, assuming processors have unique identifiers of size $O(\log n)$, where $n$ is the number of processors. It elects a leader in $O(D +\log n)$ rounds, where $D$ is the diameter of the network, with messages of size $O(1)$. Thus it has a bit round complexity of $O(D +\log n)$. This substantially improves upon the best known algorithm whose bit round complexity is $O(D\log n)$. In fact, using the lower bound by Kutten et al. (2015) and a result of Dinitz and Solomon (2007), we show that the bit round complexity of \STT is optimal (up to a constant factor), which is a significant step forward in understanding the interplay between time and message optimality for the election problem. Our algorithm requires no knowledge on the graph such as $n$ or $D$, and the pipelining technique we introduce to break the $O(D\log n)$ barrier is general.
△ Less
Submitted 7 September, 2018; v1 submitted 6 May, 2016;
originally announced May 2016.
-
Efficiently Testing T-Interval Connectivity in Dynamic Graphs
Authors:
Arnaud Casteigts,
Ralf Klasing,
Yessin M. Neggaz,
Joseph G. Peters
Abstract:
Many types of dynamic networks are made up of durable entities whose links evolve over time. When considered from a {\em global} and {\em discrete} standpoint, these networks are often modelled as evolving graphs, i.e. a sequence of graphs ${\cal G}=(G_1,G_2,...,G_δ)$ such that $G_i=(V,E_i)$ represents the network topology at time step $i$. Such a sequence is said to be $T$-interval connected if f…
▽ More
Many types of dynamic networks are made up of durable entities whose links evolve over time. When considered from a {\em global} and {\em discrete} standpoint, these networks are often modelled as evolving graphs, i.e. a sequence of graphs ${\cal G}=(G_1,G_2,...,G_δ)$ such that $G_i=(V,E_i)$ represents the network topology at time step $i$. Such a sequence is said to be $T$-interval connected if for any $t\in [1, δ-T+1]$ all graphs in $\{G_t,G_{t+1},...,G_{t+T-1}\}$ share a common connected spanning subgraph. In this paper, we consider the problem of deciding whether a given sequence ${\cal G}$ is $T$-interval connected for a given $T$. We also consider the related problem of finding the largest $T$ for which a given ${\cal G}$ is $T$-interval connected. We assume that the changes between two consecutive graphs are arbitrary, and that two operations, {\em binary intersection} and {\em connectivity testing}, are available to solve the problems. We show that $Ω(δ)$ such operations are required to solve both problems, and we present optimal $O(δ)$ online algorithms for both problems. We extend our online algorithms to a dynamic setting in which connectivity is based on the recent evolution of the network.
△ Less
Submitted 17 March, 2017; v1 submitted 31 January, 2015;
originally announced February 2015.
-
Maintaining a Distributed Spanning Forest in Highly Dynamic Networks
Authors:
Matthieu Barjon,
Arnaud Casteigts,
Serge Chaumette,
Colette Johnen,
Yessin M. Neggaz
Abstract:
Highly dynamic networks are characterized by frequent changes in the availability of communication links. These networks are often partitioned into several components, which split and merge unpredictably. We present a distributed algorithm that maintains a forest of (as few as possible) spanning trees in such a network, with no restriction on the rate of change. Our algorithm is inspired by high-l…
▽ More
Highly dynamic networks are characterized by frequent changes in the availability of communication links. These networks are often partitioned into several components, which split and merge unpredictably. We present a distributed algorithm that maintains a forest of (as few as possible) spanning trees in such a network, with no restriction on the rate of change. Our algorithm is inspired by high-level graph transformations, which we adapt here in a (synchronous) message passing model for dynamic networks. The resulting algorithm has the following properties: First, every decision is purely local---in each round, a node only considers its role and that of its neighbors in the tree, with no further information propagation (in particular, no wave mechanisms). Second, whatever the rate and scale of the changes, the algorithm guarantees that, by the end of every round, the network is covered by a forest of spanning trees in which 1) no cycle occur, 2) every node belongs to exactly one tree, and 3) every tree contains exactly one root (or token). We primarily focus on the correctness of this algorithm, which is established rigorously. While performance is not the main focus, we suggest new complexity metrics for such problems, and report on preliminary experimentation results validating our algorithm in a practical scenario.
△ Less
Submitted 24 October, 2017; v1 submitted 16 October, 2014;
originally announced October 2014.
-
Un algorithme de test pour la connexité temporelle des graphes dynamiques de faible densité
Authors:
Matthieu Barjon,
Arnaud Casteigts,
Serge Chaumette,
Colette Johnen,
Yessin M. Neggaz
Abstract:
We address the problem of testing whether a dynamic graph is temporally connected, i.e. a temporal path ({\em journey}) exists between all pairs of vertices. We consider a discrete version of the problem, where the topology is given as an evolving graph $\G=\{G_1,G_2,...,G_{k}\}$ in which only the set of (directed) edges varies. Two cases are studied, depending on whether a single edge or an unlim…
▽ More
We address the problem of testing whether a dynamic graph is temporally connected, i.e. a temporal path ({\em journey}) exists between all pairs of vertices. We consider a discrete version of the problem, where the topology is given as an evolving graph $\G=\{G_1,G_2,...,G_{k}\}$ in which only the set of (directed) edges varies. Two cases are studied, depending on whether a single edge or an unlimited number of edges can be crossed in a same $G_i$ (strict journeys {\it vs} non-strict journeys). For strict journeys, two existing algorithms designed for other problems can be adapted. However, we show that a dedicated approach achieves a better time complexity than one of these two algorithms in all cases, and than the other one for those graphs whose density is low at any time (though arbitrary over time). The time complexity of our algorithm is $O(kμn)$, where $k=|\G|$ is the number of time steps and $μ=max(|E_i|)$ is the maximum {\em instant} density, to be contrasted with $m=|\cup E_i|$, the {\em cumulated} density. Indeed, it is not uncommon for a mobility scenario to satisfy, for instance, both $μ=o(n)$ and $m=Θ(n^2)$. We characterize the key values of $k, μ$ and $m$ for which our algorithm should be used. For non-strict journeys, for which no algorithm is known, we show that a similar strategy can be used to answer the question, still in $O(kμn)$ time.
△ Less
Submitted 1 May, 2014;
originally announced May 2014.
-
Testing Temporal Connectivity in Sparse Dynamic Graphs
Authors:
Matthieu Barjon,
Arnaud Casteigts,
Serge Chaumette,
Colette Johnen,
Yessin M. Neggaz
Abstract:
We address the problem of testing whether a given dynamic graph is temporally connected, {\it i.e} a temporal path (also called a {\em journey}) exists between all pairs of vertices. We consider a discrete version of the problem, where the topology is given as an evolving graph ${\cal G}=\{G_1,G_2,...,G_{k}\}$ whose set of vertices is invariant and the set of (directed) edges varies over time. Two…
▽ More
We address the problem of testing whether a given dynamic graph is temporally connected, {\it i.e} a temporal path (also called a {\em journey}) exists between all pairs of vertices. We consider a discrete version of the problem, where the topology is given as an evolving graph ${\cal G}=\{G_1,G_2,...,G_{k}\}$ whose set of vertices is invariant and the set of (directed) edges varies over time. Two cases are studied, depending on whether a single edge or an unlimited number of edges can be crossed in a same $G_i$ (strict journeys {\it vs} non-strict journeys).
In the case of {\em strict} journeys, a number of existing algorithms designed for more general problems can be adapted. We adapt one of them to the above formulation of the problem and characterize its running time complexity. The parameters of interest are the length of the graph sequence $k=|{\cal G}|$, the maximum {\em instant} density $μ=max(|E_i|)$, and the {\em cumulated} density $m=|\cup E_i|$. Our algorithm has a time complexity of $O(kμn)$, where $n$ is the number of nodes. This complexity is compared to that of the other solutions: one is always more costly (keep in mind that is solves a more general problem), the other one is more or less costly depending on the interplay between instant density and cumulated density. The length $k$ of the sequence also plays a role. We characterize the key values of $k, μ$ and $m$ for which either algorithm should be used.
In the case of {\em non-strict} journeys, for which no algorithm is known, we show that some pre-processing of the input graph allows us to re-use the same algorithm than before. By chance, these operations happens to cost again $O(kμn)$ time, which implies that the second problem is not more difficult than the first.
△ Less
Submitted 5 August, 2014; v1 submitted 30 April, 2014;
originally announced April 2014.
-
Shortest, Fastest, and Foremost Broadcast in Dynamic Networks
Authors:
Arnaud Casteigts,
Paola Flocchini,
Bernard Mans,
Nicola Santoro
Abstract:
Highly dynamic networks rarely offer end-to-end connectivity at a given time. Yet, connectivity in these networks can be established over time and space, based on temporal analogues of multi-hop paths (also called {\em journeys}). Attempting to optimize the selection of the journeys in these networks naturally leads to the study of three cases: shortest (minimum hop), fastest (minimum duration), a…
▽ More
Highly dynamic networks rarely offer end-to-end connectivity at a given time. Yet, connectivity in these networks can be established over time and space, based on temporal analogues of multi-hop paths (also called {\em journeys}). Attempting to optimize the selection of the journeys in these networks naturally leads to the study of three cases: shortest (minimum hop), fastest (minimum duration), and foremost (earliest arrival) journeys. Efficient centralized algorithms exists to compute all cases, when the full knowledge of the network evolution is given.
In this paper, we study the {\em distributed} counterparts of these problems, i.e. shortest, fastest, and foremost broadcast with termination detection (TDB), with minimal knowledge on the topology.
We show that the feasibility of each of these problems requires distinct features on the evolution, through identifying three classes of dynamic graphs wherein the problems become gradually feasible: graphs in which the re-appearance of edges is {\em recurrent} (class R), {\em bounded-recurrent} (B), or {\em periodic} (P), together with specific knowledge that are respectively $n$ (the number of nodes), $Δ$ (a bound on the recurrence time), and $p$ (the period). In these classes it is not required that all pairs of nodes get in contact -- only that the overall {\em footprint} of the graph is connected over time.
Our results, together with the strict inclusion between $P$, $B$, and $R$, implies a feasibility order among the three variants of the problem, i.e. TDB[foremost] requires weaker assumptions on the topology dynamics than TDB[shortest], which itself requires less than TDB[fastest]. Reversely, these differences in feasibility imply that the computational powers of $R_n$, $B_Δ$, and $P_p$ also form a strict hierarchy.
△ Less
Submitted 27 August, 2014; v1 submitted 11 October, 2012;
originally announced October 2012.
-
Expressivity of Time-Varying Graphs and the Power of Waiting in Dynamic Networks
Authors:
Arnaud Casteigts,
Paola Flocchini,
Emmanuel Godard,
Nicola Santoro,
Masafumi Yamashita
Abstract:
In infrastructure-less highly dynamic networks, computing and performing even basic tasks (such as routing and broadcasting) is a very challenging activity due to the fact that connectivity does not necessarily hold, and the network may actually be disconnected at every time instant. Clearly the task of designing protocols for these networks is less difficult if the environment allows waiting (i.e…
▽ More
In infrastructure-less highly dynamic networks, computing and performing even basic tasks (such as routing and broadcasting) is a very challenging activity due to the fact that connectivity does not necessarily hold, and the network may actually be disconnected at every time instant. Clearly the task of designing protocols for these networks is less difficult if the environment allows waiting (i.e., it provides the nodes with store-carry-forward-like mechanisms such as local buffering) than if waiting is not feasible. No quantitative corroborations of this fact exist (e.g., no answer to the question: how much easier?). In this paper, we consider these qualitative questions about dynamic networks, modeled as time-varying (or evolving) graphs, where edges exist only at some times.
We examine the difficulty of the environment in terms of the expressivity of the corresponding time-varying graph; that is in terms of the language generated by the feasible journeys in the graph. We prove that the set of languages $L_{nowait}$ when no waiting is allowed contains all computable languages. On the other end, using algebraic properties of quasi-orders, we prove that $L_{wait}$ is just the family of regular languages. In other words, we prove that, when waiting is no longer forbidden, the power of the accepting automaton (difficulty of the environment) drops drastically from being as powerful as a Turing machine, to becoming that of a Finite-State machine. This (perhaps surprisingly large) gap is a measure of the computational power of waiting.
We also study bounded waiting; that is when waiting is allowed at a node only for at most $d$ time units. We prove the negative result that $L_{wait[d]} = L_{nowait}$; that is, the expressivity decreases only if the waiting is finite but unpredictable (i.e., under the control of the protocol designer and not of the environment).
△ Less
Submitted 9 May, 2012;
originally announced May 2012.
-
Building Fastest Broadcast Trees in Periodically-Varying Graphs
Authors:
Arnaud Casteigts,
Paola Flocchini,
Bernard Mans,
Nicola Santoro
Abstract:
Delay-tolerant networks (DTNs) are characterized by a possible absence of end-to-end communication routes at any instant. Still, connectivity can generally be established over time and space. The optimality of a temporal path (journey) in this context can be defined in several terms, including topological (e.g. {\em shortest} in hops) and temporal (e.g. {\em fastest, foremost}). The combinatorial…
▽ More
Delay-tolerant networks (DTNs) are characterized by a possible absence of end-to-end communication routes at any instant. Still, connectivity can generally be established over time and space. The optimality of a temporal path (journey) in this context can be defined in several terms, including topological (e.g. {\em shortest} in hops) and temporal (e.g. {\em fastest, foremost}). The combinatorial problem of computing shortest, foremost, and fastest journeys {\em given full knowledge} of the network schedule was addressed a decade ago (Bui-Xuan {\it et al.}, 2003). A recent line of research has focused on the distributed version of this problem, where foremost, shortest or fastest {\em broadcast} are performed without knowing the schedule beforehand. In this paper we show how to build {\em fastest} broadcast trees (i.e., trees that minimize the global duration of the broadcast, however late the departure is) in Time-Varying Graphs where intermittent edges are available periodically (it is known that the problem is infeasible in the general case even if various parameters of the graph are know). We address the general case where contacts between nodes can have arbitrary durations and thus fastest routes may consist of a mixture of {\em continuous} and {\em discontinuous} segments (a more complex scenario than when contacts are {\em punctual} and thus routes are only discontinuous). Using the abstraction of \tclocks to compute the temporal distances, we solve the fastest broadcast problem by first learning, at the emitter, what is its time of {\em minimum temporal eccentricity} (i.e. the fastest time to reach all the other nodes), and second by building a {\em foremost} broadcast tree relative to this particular emission date.
△ Less
Submitted 13 April, 2012;
originally announced April 2012.
-
On the Feasibility of Maintenance Algorithms in Dynamic Graphs
Authors:
Arnaud Casteigts,
Bernard Mans,
Luke Mathieson
Abstract:
Near ubiquitous mobile computing has led to intense interest in dynamic graph theory. This provides a new and challenging setting for algorithmics and complexity theory. For any graph-based problem, the rapid evolution of a (possibly disconnected) graph over time naturally leads to the important complexity question: is it better to calculate a new solution from scratch or to adapt the known soluti…
▽ More
Near ubiquitous mobile computing has led to intense interest in dynamic graph theory. This provides a new and challenging setting for algorithmics and complexity theory. For any graph-based problem, the rapid evolution of a (possibly disconnected) graph over time naturally leads to the important complexity question: is it better to calculate a new solution from scratch or to adapt the known solution on the prior graph to quickly provide a solution of guaranteed quality for the changed graph?
In this paper, we demonstrate that the former is the best approach in some cases, but that there are cases where the latter is feasible. We prove that, under certain conditions, hard problems cannot even be approximated in any reasonable complexity bound --- i.e., even with a large amount of time, having a solution to a very similar graph does not help in computing a solution to the current graph. To achieve this, we formalize the idea as a maintenance algorithm. Using r-Regular Subgraph as the primary example we show that W[1]-hardness for the parameterized approximation problem implies the non-existence of a maintenance algorithm for the given approximation ratio. Conversely we show that Vertex Cover, which is fixed-parameter tractable, has a 2-approximate maintenance algorithm. The implications of NP-hardness and NPO-hardness are also explored.
△ Less
Submitted 17 February, 2012; v1 submitted 13 July, 2011;
originally announced July 2011.
-
Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks
Authors:
Arnaud Casteigts,
Serge Chaumette,
Afonso Ferreira
Abstract:
Besides the complexity in time or in number of messages, a common approach for analyzing distributed algorithms is to look at the assumptions they make on the underlying network. We investigate this question from the perspective of network dynamics. In particular, we ask how a given property on the evolution of the network can be rigorously proven as necessary or sufficient for a given algorithm.…
▽ More
Besides the complexity in time or in number of messages, a common approach for analyzing distributed algorithms is to look at the assumptions they make on the underlying network. We investigate this question from the perspective of network dynamics. In particular, we ask how a given property on the evolution of the network can be rigorously proven as necessary or sufficient for a given algorithm. The main contribution of this paper is to propose the combination of two existing tools in this direction: local computations by means of graph relabelings, and evolving graphs. Such a combination makes it possible to express fine-grained properties on the network dynamics, then examine what impact those properties have on the execution at a precise, intertwined, level. We illustrate the use of this framework through the analysis of three simple algorithms, then discuss general implications of this work, which include (i) the possibility to compare distributed algorithms on the basis of their topological requirements, (ii) a formal hierarchy of dynamic networks based on these requirements, and (iii) the potential for mechanization induced by our framework, which we believe opens a door towards automated analysis and decision support in dynamic networks.
△ Less
Submitted 1 May, 2014; v1 submitted 27 February, 2011;
originally announced February 2011.
-
Time-Varying Graphs and Social Network Analysis: Temporal Indicators and Metrics
Authors:
Nicola Santoro,
Walter Quattrociocchi,
Paola Flocchini,
Arnaud Casteigts,
Frederic Amblard
Abstract:
Most instruments - formalisms, concepts, and metrics - for social networks analysis fail to capture their dynamics. Typical systems exhibit different scales of dynamics, ranging from the fine-grain dynamics of interactions (which recently led researchers to consider temporal versions of distance, connectivity, and related indicators), to the evolution of network properties over longer periods of t…
▽ More
Most instruments - formalisms, concepts, and metrics - for social networks analysis fail to capture their dynamics. Typical systems exhibit different scales of dynamics, ranging from the fine-grain dynamics of interactions (which recently led researchers to consider temporal versions of distance, connectivity, and related indicators), to the evolution of network properties over longer periods of time. This paper proposes a general approach to study that evolution for both atemporal and temporal indicators, based respectively on sequences of static graphs and sequences of time-varying graphs that cover successive time-windows. All the concepts and indicators, some of which are new, are expressed using a time-varying graph formalism.
△ Less
Submitted 3 February, 2011;
originally announced February 2011.
-
Time-Varying Graphs and Dynamic Networks
Authors:
Arnaud Casteigts,
Paola Flocchini,
Walter Quattrociocchi,
Nicola Santoro
Abstract:
The past few years have seen intensive research efforts carried out in some apparently unrelated areas of dynamic systems -- delay-tolerant networks, opportunistic-mobility networks, social networks -- obtaining closely related insights. Indeed, the concepts discovered in these investigations can be viewed as parts of the same conceptual universe; and the formal models proposed so far to express s…
▽ More
The past few years have seen intensive research efforts carried out in some apparently unrelated areas of dynamic systems -- delay-tolerant networks, opportunistic-mobility networks, social networks -- obtaining closely related insights. Indeed, the concepts discovered in these investigations can be viewed as parts of the same conceptual universe; and the formal models proposed so far to express some specific concepts are components of a larger formal description of this universe. The main contribution of this paper is to integrate the vast collection of concepts, formalisms, and results found in the literature into a unified framework, which we call TVG (for time-varying graphs). Using this framework, it is possible to express directly in the same formalism not only the concepts common to all those different areas, but also those specific to each. Based on this definitional work, employing both existing results and original observations, we present a hierarchical classification of TVGs; each class corresponds to a significant property examined in the distributed computing literature. We then examine how TVGs can be used to study the evolution of network properties, and propose different techniques, depending on whether the indicators for these properties are a-temporal (as in the majority of existing studies) or temporal. Finally, we briefly discuss the introduction of randomness in TVGs.
△ Less
Submitted 17 February, 2012; v1 submitted 30 November, 2010;
originally announced December 2010.
-
Construction et maintien d'une forêt couvrante dans un réseau dynamique
Authors:
Yoann Pigné,
Arnaud Casteigts,
Frédéric Guinand,
Serge Chaumette
Abstract:
In this work we introduce the principles of an algorithm that constructs and maintains a spanning forest in a mobile telecommunication network-a MANET. The algorithm is based on the random walk of a token and is entirely decentralized. A probability analysis is performed when the network is static. Then we show that performances can be slightly enhanced when adding a memory process in the walk on…
▽ More
In this work we introduce the principles of an algorithm that constructs and maintains a spanning forest in a mobile telecommunication network-a MANET. The algorithm is based on the random walk of a token and is entirely decentralized. A probability analysis is performed when the network is static. Then we show that performances can be slightly enhanced when adding a memory process in the walk on the token.
△ Less
Submitted 31 May, 2010;
originally announced May 2010.
-
JBotSim, a Tool for Fast Prototyping of Distributed Algorithms in Dynamic Networks
Authors:
Arnaud Casteigts,
Rémi Laplace
Abstract:
JBotSim is a java library that offers basic primitives for prototyping, running, and visualizing distributed algorithms in dynamic networks. With JBotSim, one can implement an idea in minutes and interact with it ({\it e.g. }, add, move, or delete nodes) while it is running. JBotSim is well suited to prepare live demonstrations of your algorithms to colleagues or students; it can also be used to e…
▽ More
JBotSim is a java library that offers basic primitives for prototyping, running, and visualizing distributed algorithms in dynamic networks. With JBotSim, one can implement an idea in minutes and interact with it ({\it e.g. }, add, move, or delete nodes) while it is running. JBotSim is well suited to prepare live demonstrations of your algorithms to colleagues or students; it can also be used to evaluate performance at the algorithmic level (number of messages, number of rounds, etc.). Unlike most tools, JBotSim is not an integrated environment. It is a lightweight library to be used in your program. In this paper, we present an overview of its distinctive features and architecture.
△ Less
Submitted 25 September, 2019; v1 submitted 9 January, 2010;
originally announced January 2010.
-
Distributed Maintenance of Anytime Available Spanning Trees in Dynamic Networks
Authors:
Arnaud Casteigts,
Serge Chaumette,
Frédéric Guinand,
Yoann Pigné
Abstract:
We address the problem of building and maintaining distributed spanning trees in highly dynamic networks, in which topological events can occur at any time and any rate, and no stable periods can be assumed. In these harsh environments, we strive to preserve some properties such as cycle-freeness or the existence of a root in each tree, in order to make it possible to keep using the trees uninterr…
▽ More
We address the problem of building and maintaining distributed spanning trees in highly dynamic networks, in which topological events can occur at any time and any rate, and no stable periods can be assumed. In these harsh environments, we strive to preserve some properties such as cycle-freeness or the existence of a root in each tree, in order to make it possible to keep using the trees uninterruptedly (to a possible extent). Our algorithm operates at a coarse-grain level, using atomic pairwise interactions in a way akin to recent population protocol models. The algorithm relies on a perpetual alternation of \emph{topology-induced splittings} and \emph{computation-induced mergings} of a forest of spanning trees. Each tree in the forest hosts exactly one token (also called root) that performs a random walk {\em inside} the tree, switching parent-child relationships as it crosses edges. When two tokens are located on both sides of a same edge, their trees are merged upon this edge and one token disappears. Whenever an edge that belongs to a tree disappears, its child endpoint regenerates a new token instantly. The main features of this approach is that both \emph{merging} and \emph{splitting} are purely localized phenomenons. In this paper, we present and motivate the algorithm, and we prove its correctness in arbitrary dynamic networks. Then we discuss several implementation choices around this general principle. Preliminary results regarding its analysis are also discussed, in particular an analytical expression of the expected merging time for two given trees in a static context.
△ Less
Submitted 22 July, 2013; v1 submitted 20 April, 2009;
originally announced April 2009.
