Arnaud Casteigts - LaBRI

Arnaud Casteigts
Are you Arnaud Casteigts?

Claim your profile, edit publications, add additional information:

Contact Details

Arnaud Casteigts

Pubs By Year

External Links

Pub Categories

Computer Science - Distributed; Parallel; and Cluster Computing (14)
Computer Science - Data Structures and Algorithms (6)
Computer Science - Networking and Internet Architecture (6)
Physics - Physics and Society (2)
Computer Science - Computational Complexity (2)
Computer Science - Mathematical Software (1)
Computer Science - Discrete Mathematics (1)
Computer Science - Artificial Intelligence (1)
Computer Science - Computation and Language (1)

Publications Authored By Arnaud Casteigts

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. Read 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. Read 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)$. Read 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. Read More

Highly dynamic networks are characterized by frequent changes in the availability of communication links. Many of these networks are in general partitioned into several components that keep splitting and merging continuously and unpredictably. We present an algorithm that strives to maintain a forest of spanning trees in such networks, without any kind of assumption on the rate of changes. Read 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. Read 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,. Read 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. Read 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. Read 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. Read 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. Read 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. Read 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. Read 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). Read 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. Read 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. Read 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. Read More