The Dancing problem requires a swarm of n autonomous mobile robots to form a sequence of patterns, i.e., perform a choreography. Existing work has proven that some crucial restrictions on choreographies and initial configurations (e.g., on repetitions of patterns, periodicity, symmetries, contractions/expansions) must hold so that the Dancing problem can be solved under certain robot models. Here, we prove that these necessary constraints can be dropped by considering the $$\mathcal {LUMI}$$ model (i.e., where robots are endowed with a light whose color can be chosen from a constant-size palette) under the quite unexplored sequential scheduler. We formalize the class of Universal Dancing problems which require a swarm of n robots starting from any initial configuration to perform a (periodic or finite) sequence of arbitrary patterns, only provided that each pattern consists of n vertices (including multiplicities). However, we prove that, to be solvable under $$\mathcal {LUMI}$$ , the length of the feasible choreographies is bounded by the compositions of n into the number of colors available to the robots. We provide an algorithm solving Universal Dancing by exploiting the peculiar capability of sequential robots to implement a distributed counter. Even assuming non-rigid movements, our algorithm ensures spatial homogeneity of the performed choreography.

We study the dispersion problem for k mobile agents on an n-node anonymous, memory-less graph with maximum degree Δ. Agents must autonomously relocate so that no two agents occupy the same node. While an optimal O(k)-time, O(log(k + Δ))-memory algorithm is known under synchronous settings, the best known asynchronous algorithm requires O(k log min {k, Δ}) time due to the difficulty of distinguishing unvisited nodes from nodes temporarily vacated by agents. We close this gap by presenting the first fully asynchronous algorithm achieving asymptotically optimal O(k) time and O(log(k + Δ)) memory. Our main technical contribution is the Port-1 Tree (P1Tree), a novel structural property of a port-labeled graph. By forcing the DFS traversal to prioritize edges locally labeled with port 1, P1Tree allows agents to verify the status of neighboring nodes in O(1) asynchronous epochs without relying on timing assumptions or oscillations used in synchronous settings. We show that this approach yields optimal bounds for both rooted and general initial configurations.

We provide the following new results on maximal k-edge-connected subgraphs of undirected graphs. (1) A general framework for maintaining the maximal k-edge-connected subgraphs upon insertions of edges or vertices, by successively partitioning the graph into its k-edge-connected components. This defines a decomposition tree, which can be maintained by using algorithms for the incremental maintenance of the k-edge-connected components as black boxes at every level of the tree. As a concrete application of this framework, we provide two algorithms for the incremental maintenance of the maximal 3-edge-connected subgraphs. These algorithms allow for vertex and edge insertions, interspersed with queries asking whether two vertices belong to the same maximal 3-edge-connected subgraph, and there is a trade-off between their time-and space-complexity. Specifically, the first algorithm has O (m alpha (m, n) + n2 log2 n) total running time and uses O(n) space, where m is the number of edge insertions and queries, and n is the total number of vertices inserted starting from an empty graph. The second algorithm performs the same operations in faster O (m alpha (m, n) +n2 alpha (n, n)) time in total, using O(n2) space. (2) We provide efficient constructions of (almost) sparse spanning subgraphs that have the same maximal k-edge-connected subgraphs as the original graph. We refer to such subgraphs as k-certificates. We use those certificates to speed up the computation of the maximal k-edge-connected subgraphs in the static and the fully-dynamic setting. (3) Finally, we give a simple reduction for computing the maximal k-edge-connected subgraphs to a fully dynamic mincut algorithm. (c) 2026 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

In networked systems supporting mobile agents, a particularly dangerous security threat facing the agents is the presence of a black hole (Bh): a network host that destroys any incoming agent without leaving any trace. The problem, called Black hole search (Bhs), of efficiently determining the location of such a dangerous host has been extensively studied under a variety of different assumptions. In spite of their differences, the existing results share the same assumption that all the searching agents are reliable.In this paper, we start the investigation of the Bhs problem when some of the searching agents are faulty in a malicious way. More precisely, we consider that up to f of the k searching agents are Byzantine: they may behave in an arbitrary manner, actively misleading other agents; furthermore, they are in collusion with the black hole, and immune to its destructive power.We study under what conditions the Bhs problem can be solved in a synchronous network of arbitrary topology in spite of the malicious agents, examining the impact on complexity of two factors: the a-priori topological knowledge held by the agents, and the communication mechanism available to them.We prove that, with prior knowledge about the graph topology (i.e., a network map), Bhs can be solved by k ≥ 2f +2 agents in O(n + f) synchronous rounds both with whiteboards and with just local communication, where n is the number of nodes in the network.Without any knowledge about the topological structure, using whiteboard communication Bhs can be solved by k ≥ (f+1)(∆+ 1) agents in O(m+f) rounds; instead, using local communication, Bhs can be solved by k ≥ (f + 1)(∆ + 1) + 3f + 1 agents in O(m • n + f) rounds, where m is the number of links of the network and ∆ is the maximum degree of the network.In all cases, as we show, the bound on the total number k of agents is asymptotically optimal.

The dispersion problem has received much attention recently in the distributed computing literature. In this problem, k ≤ n agents placed initially arbitrarily on the nodes of an n-node, m-edge anonymous graph of maximum degree Δ have to reposition autonomously to reach a configuration in which each agent is on a distinct node of the graph. Dispersion is interesting as well as important due to its connections to many fundamental coordination problems by mobile agents on graphs, such as exploration, scattering, load balancing, relocation of self-driven electric cars (robots) to recharge stations (nodes), etc. The objective has been to provide a solution that optimizes simultaneously time and memory complexities. There exist graphs for which the lower bound on time complexity is Ω(k). Memory complexity is Ω(log k) per agent independent of graph topology. The state-of-the-art algorithms have (i) time complexity O(k log2 k) and memory complexity O(log(k + Δ)) under the synchronous setting [DISC'24] and (ii) time complexity O(min{m, kΔ}) and memory complexity O(log(k + Δ)) under the asynchronous setting [OPODIS'21]. In this paper, we improve substantially on this state-of-the-art. Under the synchronous setting as in [DISC'24], we present the first optimal O(k) time algorithm keeping memory complexity O(log(k + Δ)). Under the asynchronous setting as in [OPODIS'21], we present the first algorithm with time complexity O(k log k) keeping memory complexity O(log(k + Δ)), which is time-optimal within an O(log k) factor despite asynchrony. Both the results were obtained through novel techniques to quickly find empty nodes to settle agents, which may be of independent interest.

The Dancing problem requires a swarm of n autonomous mobile robots to form a sequence of patterns, aka perform a choreography.Existing work has proven that some crucial restrictions on choreographies and initial configurations (e.g., on repetitions of patterns, periodicity, symmetries, contractions/expansions) must hold so that the Dancing problem can be solved under certain robot models.Here, we prove that these necessary constraints can be dropped by considering the LUMI model (i.e., where robots are endowed with a light whose color can be chosen from a constant-size palette) under the quite unexplored sequential scheduler.We formalize the class of Universal Dancing problems which require a swarm of n robots starting from any initial configuration to perform a (periodic or finite) sequence of arbitrary patterns, only provided that each pattern consists of n vertices (including multiplicities).However, we prove that, to be solvable under LUMI, the length of the feasible choreographies is bounded by the compositions of n into the number of colors available to the robots.We provide an algorithm solving the Universal Dancing problem by exploiting the peculiar capability of sequential robots to implement a distributed counter mechanism.Even assuming non-rigid movements, our algorithm ensures spatial homogeneity of the performed choreography.

We study the dispersion problem in anonymous port-labeled graphs: k ≤ n mobile agents, each with a unique ID and initially located arbitrarily on the nodes of an n-node graph with maximum degree Δ, must autonomously relocate so that no node hosts more than one agent. Dispersion serves as a fundamental task in the distributed computing of mobile agents, and its complexity stems from key challenges in local coordination under anonymity and limited memory. The goal is to minimize both the time to achieve dispersion and the memory required per agent. It is known that any algorithm requires Ω(k) time in the worst case, and Ω(log k) bits of memory per agent. A recent result [Kshemkalyani et al., 2025] gives an optimal O(k)-time algorithm in the synchronous setting and an O(k log k)-time algorithm in the asynchronous setting, both using O(log(k+Δ)) bits. We close the complexity gap in the asynchronous setting by presenting the first dispersion algorithm that runs in optimal O(k) time using O(log(k+Δ)) bits of memory per agent. Our solution relies on a novel technique for constructing a port-one tree in anonymous graphs, which may be of independent interest.

Given any arbitrary initial configuration of k ≤ n robots positioned on the nodes of an n -node anonymous graph, the problem of dispersion is to autonomously reposition the robots such that each node will contain at most one robot. This problem gained significant interest due to its resemblance with several fundamental problems such as exploration, scattering, load balancing, relocation of electric cars to charging stations, etc. The objective is to solve dispersion simultaneously minimizing (or providing trade-off between) time and memory requirement at each robot. The literature mainly dealt with dispersion on undirected anonymous graphs. In this paper, we initiate the study of dispersion on directed anonymous graphs. We first show that it may not always be possible to solve dispersion when the directed graph is not strongly connected. We then establish some lower bounds on both time and memory requirement at each robot for solving dispersion on a strongly connected directed graph. Finally, we provide three deterministic algorithms solving dispersion on any strongly connected directed graph. Let D be the graph diameter, Δ o u t be its maximum out-degree, and d be the deficiency (the minimum number of edges needed to add to the graph to make it Eulerian). The first algorithm solves dispersion in O ( d ⋅ k 2 ) time with O ( k ⋅ log ⁡ ( k + Δ o u t ) ) bits at each robot. The second algorithm solves dispersion in O ( k 2 ⋅ Δ o u t ) time with O ( log ⁡ ( k + Δ o u t ) ) bits at each robot. The third algorithm solves dispersion in O ( k ⋅ D ) time with O ( k ⋅ log ⁡ ( k + Δ o u t ) ) bits at each robot, provided that robots in the 1-hop neighborhood can communicate. All three algorithms extend to handle crash faults.

We consider the distributed setting of n autonomous mobile robots operating in Look-Compute-Move (LCM) cycles on a plane. Robots are equipped with lights (i.e., the robots with lights model) that can assume a color at a time from a fixed color set. We consider obstructed visibility in which a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. Robots are said to collide if they share positions or their paths intersect within concurrent LCM cycles. In this paper, we consider the problem of Uniform Circle Formation, where starting from distinct initial locations in the plane, the robots relocate autonomously to occupy positions on the vertices of a regular n-gon not fixed in advance. The objective is to simultaneously minimize (or provide tradeoff between) two fundamental performance metrics: (i) time to solve Uniform Circle Formation and (ii) size of the color set used by each robot light. There exists an O(1)-time O(1)-color algorithm for this problem in the fully synchronous and semi-synchronous settings and O(log n)-time O(1)-color algorithm in the asynchronous setting, avoiding collisions. In this paper, we consider the asynchronous setting and develop a deterministic generic algorithmic framework that provides time-color tradeoff on solving Uniform Circle Formation avoiding collisions. Specifically, our framework achieves a solution with time O(x) using $O\left( {{n^{1/{2^x}}}} \right)$ colors in the asynchronous setting. Setting x some constant, we achieve the first asynchronous, asymptotically time-optimal, algorithm with O(1) time using $O(\sqrt n )$ colors, whereas setting x = O(log log n), we) achieve the second asynchronous, asymptotically color-optimal, algorithm with O(log log n time using O(1) colors. In sum, our framework shows the size of the color set provides a tradeoff on time for Uniform Circle Formation in the asynchronous setting.

Abstract This paper considers the area convergence problem, which requires a group of robots to gather in a small area not defined a priori. While it is known that robots can gather at a point if they can precisely measure distances, we, in this paper, show that without any agreement on the coordinate system, it is impossible for robots to converge to an area if they cannot measure distances or angles. We denote these robots without the ability to measure distances or angles as monoculus robots. We present a counterexample showing that monoculus robots fail in area convergence even with the capability of measuring angles. However, monoculus robots with a weak notion of distance or minimal agreement on the coordinate system are sufficient to achieve area convergence. In particular, we present area convergence algorithms in asynchronous model for such monoculus robots with one of the two following simple additional capabilities: (1) locality detection ($\mathcal{L}\mathcal{D}$), a notion of distance or (2) orthogonal line agreement ($\mathcal{O}\mathcal{L}\mathcal{A}$), a notion of direction. We discuss extensions corresponding to multiple dimensions and the termination. Additionally, we validate our findings using simulation and show the robustness of our algorithms in the presence of errors in observation or movement.

Monitoring or surveillance needsUnmanned Aerial VehiclesorDronesto cover each point within the area of interest. In general, any outdoor region can be modeled as a surface. Thus we focus on surveillance of a surface with a random connected distribution of drones such that a reorganization of drones maximizes the covered area without creating any coverage hole. In addition, the target is to provide a compact coverage to minimize the diameter of the network formed by the drones, which helps in faster communications. We present a centralized algorithm that achieves amaximal compactcoverage. We propose two distributed algorithms based onVirtual ForceandLocal Voronoi, respectively. Extensive simulation studies show that our proposed algorithms result in hole-freemaximal compactcoverage with limited displacement. The self-organizing behavior of ourLocal Voronoibased algorithm can be replicated even in the presence of failures in the drones. The algorithm is capable of recovering a maximal coverage with the remaining non-faulty drones. Also, it is robust with respect to the addition of new drones in real-time. We finally supplement the simulation results to include churn in the network in the context of fault-tolerance and scalability.