We consider the problem of gathering in finite time and at the same location, not known beforehand, a set of deterministic semi-synchronous robots, starting from an arbitrary initial configuration that may even be bivalent (that is, a configuration where the robots are evenly split on two different locations). This problem is known to be unsolvable when the robots are oblivious, that is, when they cannot remember their past actions. We present two deterministic gathering algorithms where robots may remember and communicate a single bit of memory. This bit may be arbitrarily (and adversarially) set in the initial configuration. Our solutions are thus memory optimal and self-stabilizing. The first algorithm makes use of multiplicity detection, while the second solely uses robot colors. Their proof of correctness is formally certified by the Coq proof assistant using the Pactole framework.

We address the perpetual grid exploration (PGE) by a swarm of autonomous, asynchronous, myopic, and luminous robots. We first show that it is impossible for the robots to explore the grid regardless of their number and the number of colors they can take if their visibility range is one. We also show that PGE is impossible with three oblivious robots that have a visibility range of two hops. We then present three optimal algorithms solving the problem. The first algorithm uses four oblivious robots with a visibility range of two, but assumes they agree on a common chirality. For the two other algorithms, no common chirality is assumed. The former uses three robots that have a visibility range of two and a two-color light. The latter uses three oblivious robots under visibility range three.

In this paper, we address the problem of uniformly deploying mobile robots in complete bipartite graphs. Specifically, when n robots are positioned arbitrarily at distinct nodes in a complete bipartite graph K_{n,n}, which consists of two n-node sets V_L and V_R, the uniform deployment problem requires the robots to achieve one of the following configurations: (a) each node in V_L is occupied by exactly one robot, with no robots in V_R, or (b) each node in V_R is occupied by exactly one robot, with no robots in V_L. In either configuration, the distance between any two robots is 2, ensuring that the robots are uniformly deployed. In this paper, we explore the relationship between the visibility range of robots and the solvability of the uniform deployment problem. First, we characterize solvable and unsolvable initial configurations under the assumption that robots have an infinite visibility range. Next, we demonstrate that visibility range 1 (meaning robots can only observe nodes at a distance of 1 and the robots positioned on them) is insufficient, proving the impossibility of solving the problem under this constraint. Conversely, we show that visibility range Θ(log n) is sufficient by presenting an algorithm that solves the uniform deployment problem in O(1) rounds, starting from any solvable initial configuration. Finally, we briefly introduce an example showing that robots with a constant visibility range (which is 3 in this example) cannot solve the problem in a native way.

In this paper, we consider the exploration of an infinite grid by a swarm of fully-synchronous robots with weak capabilities: they are disoriented, opaque, do not communicate explicitely, have limited visibility, and cannot occupy the same position at the same time. Our first result shows that, in this context, minimizing the visibility range and the number of used colors are two orthogonal issues: it is impossible to design a solution to our exploration problem that is optimal w.r.t. both parameters simultaneously. Consequently, we address optimality of these two criteria separately by proposing two algorithms; the former being optimal in terms of visibility range, the latter being optimal in terms of number of used colors. More precisely, the first algorithm solves the problem using eight oblivious robots under visibility range two (this visibility being optimal when considering oblivious robots), and the second algorithm solves the problem under visibility range one using six robots and two colors (which is optimal under this visibility range). Finally, we also tackle the optimality in terms of number of robots. According to the lower bound given in Bramas et al. (2020), we propose an algorithm working with a minimum number of robots (five) under visibility range one. This latter uses twelve colors and also guarantees that nodes are visited infinitely often. • The infinite grid exclusive exploration by synchronous oblivious robots is impossible under visibility range one whatever by their number. • The infinite grid exclusive exploration can be achieved by eight synchronous oblivious robots under the optimal visibility range two. • The infinite grid exclusive exploration can be achieved by six synchronous robots under visibility range one using only two colors. • The infinite grid exclusive exploration can be achieved by only five synchronous robots under visibility range one, yet using twelve colors.

In this article, we consider DAG-based distributed ledger technologies (DLTs), i.e., DLTs where each block can reference several previous blocks hence forming a directed acyclic graph of blocks (BDAG). Each block has a weight (usually a constant normalized to one) and our goal is to compute the heaviest sub-BDAG that does not contain conflicting blocks. First, we prove that computing such a sub-BDAG is NP-complete. Then, we show that the difficulty comes from concurrent conflicts and we present an optimal algorithm that is polynomial if the number of concurrent conflicts is bounded. We also give an efficient incremental version of our algorithm. Finally, we evaluate the performance of our algorithm on random BDAGs against an existing algorithm called GHOSTDAG and show that, in addition to being optimal, our algorithm is also more efficient in practice.

Source Routing, currently facilitated by Segment Routing (SR), enables routers to add forwarding instructions to the packet to follow a particular path that deviates from the typical IGP path. These instructions form a list of detours (called segments). However, the number of segments that can be imposed at line-rate is tightly constrained by the hardware. Hence, the main challenge consists in incorporating this constraint into a path computation algorithm. The goal is to be able to solve many existing problems, including finding multi-constrained paths and re-routing packets after a failure, in a way that is deployeable in existing networks using Segment Routing. Existing solutions either lack generality, correctness, optimality, or practical computing efficiency – in particular for sparse realistic networks. In this paper, we address all such challenges with GOFOR-SR. Our framework extends usual path computation algorithms by integrating the SR constraint within the path computation itself and modifying the distance comparison method. GOFOR allows algorithm with various optimization objectives to efficiently compute optimal segment lists. Despite the loss of substructure optimality induced by SR, GOFOR proves particularly efficient, inducing only a linear overhead at worst. It also offers different strategies and path diversity options for intricate load-balancing. We formally prove the correctness and optimality of GOFOR, implement our framework for various practical use-cases, and demonstrate its performance and benefits on both real and challenging topologies.

We consider the problem of graph exploration by energy sharing mobile agents that are subject to crash faults. More precisely, we consider a team of two agents where at most one of them may fail unpredictably, and the considered topology is that of connected acyclic graphs (i.e. trees). We consider both the asynchronous and the synchronous settings, and we provide necessary and sufficient conditions about the energy.

Supporting such an all-to-all traffic matrix is challenging as it can easily lead to congestion. Scheduling patterns are designed to avoid such congestion by spreading the communications over time. The time is divided in phases and communications are spread across the phases. However, current scheduling algorithms are not fault-tolerant. In this paper we propose a fault-adaptive congestion-free scheduling to support an all-to-all exchange in fat tree topology. Our approach consist in the computation of the minimum number of communication phases required to support the all-to-all exchange with the available links, and of the scheduling of the communications on these phases. It enables to recover from failures and makes optimal use of the remaining bandwidth. We show that our scheduling approach provides better performance than the most common approach which is the Linear-shift scheduling. The throughput is improved by roughly 80% with our approach, for as little as one link failure.

The growing importance of the data in today’s applications, such as machine learning, makes merchandising them more appealing, but it opens various challenges. Indeed, we want data to be delivered in a fast, reliable, and secure manner. This means we want guarantees about the payment and the correct delivery of the data, while still offering the ease of existing publish/subscribe protocols. There exists no state-of-the-art protocol that answers to all those challenges. Most of them lack the security properties needed for merchandising data and the few secured propositions do not scale well with the number of buyers, which prevents them from global use. In this paper, we present a data payment system based on SUPRA, a publish/subscribe protocol having delivery guarantees. With our solution, it is possible to securely sell data while sharing them using the publish/subscribe model, which is known for its scalability in one-to-many communications. After presenting how our system works, we explain how it answers the various challenges of merchandising data and compare it to the other state-of-the-art solutions.

Interactions between the intra- and inter-domain routing protocols received little attention despite playing an important role in forwarding transit traffic. More precisely, by default, IGP distances are taken into account by BGP to select the closest exit gateway for the transit traffic (hot-potato routing). Upon an IGP update, the new best gateway may change and should be updated through the (full) re-convergence of BGP, causing superfluous BGP processing and updates in many cases. We propose OPTIC (Optimal Protection Technique for Inter-intra domain Convergence), an efficient way to assemble both protocols without losing the hot-potato property. OPTIC pre-computes sets of gateways (BGP next-hops) shared by groups of prefixes. Such sets are guaranteed to contain the post-convergence gateway after any single IGP event for the grouped prefixes. The new optimal exits can be found through a single walk-through of each set, allowing the transit traffic to benefit from optimal BGP routes almost as soon as the IGP converges. Compared to vanilla BGP, OPTIC's structures allow it to consider a reduced number of entries: this number can be reduced by 99% for stub networks. The update of OPTIC's structures, which is not required as long as border routers remain at least bi-connected, scales linearly in time with its number of groups.

With the growth of demands for quasi-instantaneous communication services such as real-time video streaming, cloud gaming, and industry 4.0 applications, multi-constraint Traffic Engineering (TE) becomes increasingly important. While legacy TE management planes have proven laborious to deploy, Segment Routing (SR) drastically eases the deployment of TE paths and thus became the most appropriate technology for many operators. The flexibility of SR sparked demands in ways to compute more elaborate paths. In particular, there exists a clear need in computing and deploying Delay-Constrained Least-Cost paths (DCLC) for real-time applications requiring both low delay and high bandwidth routes. However, most current DCLC solutions are heuristics not specifically tailored for SR. In this work, we leverage both inherent limitations in the accuracy of delay measurements and an operational constraint added by SR. We include these characteristics in the design of BEST2COP, an exact but efficient ECMP-aware algorithm that natively solves DCLC in SR domains. Through an extensive performance evaluation, we first show that BEST2COP scales well even in large random networks. In real networks having up to thousands of destinations, our algorithm returns all DCLC solutions encoded as SR paths in way less than a second.

The contribution of this paper is threefold. First, we give tight bounds for the complexity of the problem of data aggregation in static networks. In more details, we show that the problem remains NP-complete when the graph is of degree at most three. Second, we investigate the complexity of the same problem in a dynamic network, that is, a network whose topology can evolve through time. In the case of dynamic networks, we show that the problem is NP-complete even in the case where the graph is of degree at most two. Third, we give the first lower and upper bounds for the minimum data aggregation time in a dynamic graph. We also observe that even in a well-connected evolving graphs, the optimal solution cannot be found by a distributed algorithm or by a centralized algorithm that does not know the future.

We consider the problem of aggregating data in a dynamic graph, that is, aggregating the data that originates from all nodes in the graph to a specific node, the sink. In our model, nodes are endowed with unlimited memory and unlimited computational power. Yet, we assume that communications between nodes are carried out with pairwise interactions, where nodes can exchange control information before deciding whether they transmit their data or not, given that each node is allowed to transmit its data at most once. When a node receives a data from a neighbor, the node may aggregate it with its own data. We are interested in giving lower bounds for this problem, under two possible adversaries: the oblivious adversary, and the randomized adversary that chooses the pairwise interactions uniformly at random. For the online adaptive and the oblivious adversary, we give impossibility results when nodes have no knowledge about the graph and are not aware of the future. For the randomized adversary, we propose two optimal algorithms, (i) when nodes have no knowledge at all and (ii) when each node knows its future pairwise interactions with the sink.

We propose a new probabilistic pattern formation algorithm for oblivious mobile robots that operates in the ASYNC model. Unlike previous work, our algorithm makes no assumptions about the local coordinate systems of robots (the robots do not share a common "North" nor a common "Right"), yet it preserves the ability from any initial configuration that contains at least 5 robots to form any general pattern (and not just patterns that satisfy symmetricity predicates). Our proposal also gets rid of the previous assumption (in the same model) that robots do not pause while moving (so, our robots really are fully asynchronous), and the amount of randomness is kept low -- a single random bit per robot per Look-Compute-Move cycle is used. Our protocol consists in the combination of two phases, a probabilistic leader election phase, and a deterministic pattern formation one. As the deterministic phase does not use chirality, it may be of independent interest in the deterministic context. A noteworthy feature of our algorithm is the ability to form patterns with multiplicity points (except the gathering case due to impossibility results), a new feature in the context of pattern formation that we believe is an important asset of our approach.

Recent applications of Wireless Sensor Network require small yet sustainable battery-powered devices. As a consequence, it becomes crucial to accurately and efficiently compute a node's power consumption in order to estimate its lifetime. Existing wireless network simulators either implement simplistic energy consumption and battery models, or very complex and general ones that hinders scalability. In this paper, we (i) present WiSeBat, a module to estimate devices lifetime using realistic energy consumption and battery models, that has specially been optimized for wireless sensor network simulations. We then (ii) validate it through real measurements. Finally, we used it (iii) to compare wireless sensor lifetime in several realistic scenarios. Firstly, we review existing techniques to simulate a battery and discuss what behaviors are important to get realistic and fast simulations. We then propose simulator-independent models for the battery and for the energy consumption of sensors, and implement this model in the WSNet simulator. Secondly, we compare measured and simulated lifetimes of sensors. On the one hand, our experiments show that our models provide an 86 - 96% accurate lifetime estimation. On the other hand, the previous default WSNet models overestimate lifetime by more than 2600%. Once validated, we used our approach to benchmark the energy consumption of different protocol stacks of wireless sensor networks, under different scenarios. These simulations match well-known results in simple scenarios, as we demonstrate better performance of ContikiMAC over X-MAC. They also provide an accurate comparison of sensor lifetime in more complex scenarios.