In the distributed localisation problem (DLP), n anonymous robots (agents) A_0, ..., A_{n-1} are located at arbitrary points p_0, ..., p_{n-1} ∈ S, where S is a Euclidean space. Initially, each agent A_i operates within its own coordinate system in S, which may be inconsistent with those of other agents. The primary goal in DLP is for agents to reach a consensus on a unified (jointly agreed) coordinate system, in which all agents receive unique labels (coordinates) that accurately reflect the relative distances between all points p_0, ..., p_{n-1} in S. Extensive research on DLP has primarily focus on the feasibility and complexity of achieving consensus when agents have limited access to inter-agent distances, often due to missing or imprecise data. In contrast, this paper proposes a minimalist, computationally efficient distributed computing model where agents can query any pairwise relative positions, if needed. Specifically, we introduce a novel variant of population protocols, referred to as the spatial population protocols model. In this variant each agent can memorise one or a fixed number of coordinates, and when agents A_i and A_j interact, they can not only exchange their current knowledge but also either determine the distance d_{ij} between them in S (distance query model) or obtain the vector v_{ij} spanning points p_i and p_j (vector query model). We propose and analyse several distributed localisation protocols, including: 1) Leader-based localisation protocol with distance queries We propose and analyse two leader-based localisation protocols that stabilise silently in o(n) time. These protocols leverage an efficient solution to the novel concept of multi-contact epidemic, a natural generalisation of the core communication tool in population protocols, known as the one-way epidemic. 2) Self-stabilising leader localisation protocol with distance queries We show how to effectively utilise a leader election mechanism within the leader-based localisation protocol to get a DLP protocol that self-stabilises silently in time O(n(log n/n)^{1/(k+1)}log n) in k-dimensions. 3) Self-stabilising localisation protocol with vector queries We propose and analyse an optimally fast DLP protocol which self-stabilises silently in O(log n) time.

Utilization of alternate communication paths is a common technique to provide protection of transmission against failures of network nodes/links. However, a noticeable delay is encountered when calculating the relevant sets of disjoint paths using the available algorithms (e.g., using Bhandari's approach). This, in turn, may have a serious impact on the ability of a network to serve dynamic demands (i.e., characterized by a relatively short duration time). To provide a solution to this problem, in this article we introduce an approach to pre‐compute the sets of disjoint paths in advance to be able to start serving the demands shortly after their arrival. Our approach is based on the observation that the issue of establishing a set of node‐disjoint paths is equivalent to the problem of determining the cheapest cycle in the network topology traversing the end nodes of a demand. In particular, we propose a generalization of this scheme assuming that any pair of node‐disjoint paths can be obtained by means of merging a number of basic cycles defined for a network topology. A new method to calculate the cheapest end‐to‐end cycles based on the so called basic cycles is introduced, which, as verified for real network topologies, reduces up to 70% the time needed to establish node‐disjoint paths (compared with the results obtained for the reference Bhandari's scheme). © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(4), 308–326 2017

In this work we consider the edge searching problem for vertex-weighted graphs with arbitrarily fast and invisible fugitive. The weight function $${\omega }$$ provides for each vertex $$v$$ the minimum number of searchers required to guard $$v$$ , i.e., the fugitive may not pass through $$v$$ without being detected only if at least $${\omega }(v)$$ searchers are present at $$v$$ . This problem is a generalization of the classical edge searching problem, in which one has $${\omega }\equiv 1$$ . We assume that with a graph $$G$$ to be searched, there is associated a partition $$(V_1,\ldots ,V_t)$$ of its vertex set such that edges are allowed only within each $$V_i$$ and between two consecutive $$V_i$$ ’s. We provide an algorithm for distributed monotone connected edge searching of such graphs, where the searchers are initially placed on an arbitrary vertex of $$G$$ and have no a priori knowledge on $$G$$ , but they have a sense of direction that lets them recognize whether an edge incident to already explored vertex in $$V_i$$ leads to a vertex in one of $$V_{i-1}, V_i$$ or $$V_{i+1}$$ . Starting from any vertex the algorithm uses at most $$3\cdot \max _{i=1,\ldots ,t}{\omega }(V_i)+1$$ searchers, where $${\omega }(V_i) = \sum _{v\in V_i}{\omega }(v)$$ . We also prove that this algorithm is best possible up to a small additive constant, that is, each distributed searching algorithm in worst case must use $$3\cdot \max _{i=1,\ldots ,t}{\omega }(V_i)-1$$ searchers for some graphs.

Abstract Distributed greedy coloring is an interesting and intuitive variation of the standard coloring problem. Given an order among the colors, a coloring is said to be greedy if there does not exist a vertex for which its associated color can be replaced by a color of lower position in the fixed order without violating the property that neighboring vertices must receive different colors. We consider the problems of Greedy Coloring and Largest First Coloring (a variant of greedy coloring with strengthened constraints) in the Linial model of distributed computation, providing lower and upper bounds and a comparison to the (Δ + 1)‐Coloring and Maximal Independent Set problems, with Δ being the maximum vertex degree in G. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009