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 study distributed directory protocols for accessing shared objects in large-scale distributed systems under the recently proposed framework of learning-augmentation. Each shared object has an owner node that can modify its value. The ownership may change by moving the object from one node to another in response to move requests. The value of an object can be read by other nodes with lookup requests. The existing directory protocols were designed in the online model where both the arrival time of requests and the nodes issuing requests are not known a priori. We consider the learned-augmented framework that involves a priori knowledge on nodes that issue requests; the arrive time of requests as well as whether in fact predicted nodes issue those requests are unknown (i.e., the predictions may be error-prone). We design two distributed directory protocols, one tree-based and another cluster-based, and provide better guarantees that were known in the literature in the online model, when predictions are perfect (no prediction error). We additionally show that the guarantees degrade gracefully with prediction error but do not get worse than the guarantees in the online model even with maximum prediction error. To the best of our knowledge, this is the first study of distributed directory protocols under learning-augmented framework.

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.

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 an undirected, anonymous, port-labeled graph of n memory-less nodes, m edges, and degree Δ, we consider the problem of dispersing k ≤ n robots (or tokens) positioned initially arbitrarily on the nodes of the graph to exactly k different nodes, one on each node. The objective is to simultaneously minimize time and memory requirement at each robot. The best previously known algorithm solves this problem in O ( min ⁡ { m , k Δ } ⋅ log ⁡ ℓ ) time storing O ( log ⁡ ( k + Δ ) ) bits at each robot, where ℓ ≤ k / 2 is the number of nodes with multiple robots positioned on them in the initial configuration. In this paper, we present a novel multi-source DFS traversal algorithm solving this problem in O ( min ⁡ { m , k Δ } ) time with O ( log ⁡ ( k + Δ ) ) bits at each robot. The memory complexity of our algorithm is already asymptotically optimal and the time complexity is asymptotically optimal for the graphs of constant degree Δ = O ( 1 ) . The result holds in both synchronous and asynchronous settings.

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.

Recently, location-based social networks, that involve both social and spatial information, have received much attention in many real-world applications such as location-based services (LBS), map utilities, business planning, and so on. In this paper, we seamlessly integrate both social networks and spatial road networks, resulting in a so-called spatial-social network, and study an important and novel query type, named group planning query over spatial-social networks (GP-SSN), which is very useful for applications such as trip recommendations. In particular, a GP-SSN query retrieves a group of friends with common interests on social networks and a number of spatially close points of interest (POIs) on spatial road networks that best match group’s preferences and have the smallest traveling distances to the group. In order to tackle the GP-SSN problem, we design effective pruning methods, matching score pruning, user pruning, and distance pruning, to rule out false alarms of GP-SSN query answers and reduce the problem search space. We also propose effective indexing mechanisms to facilitate the GP-SSN query processing and develop efficient GP-SSN query answering algorithms via index traversals. Extensive experiments have been conducted to evaluate the efficiency and effectiveness of our proposed GP-SSN query processing approaches.

We consider the distributed setting of n autonomous mobile robots operating in Look-Compute-Move (LCM) cycles on the real plane. Robots may be without lights (the classic oblivious robots model) or equipped with lights (the robots with lights model). Under obstructed visibility, a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them, but it is not the case under unobstructed visibility. Robots are said to collide if they share positions or their paths intersect within concurrent LCM cycles. In this paper, we introduce and study Doorway Egress, the problem of robots exiting through a doorway from one side of a wall to the other; initially, the robots are positioned at distinct positions on one side of a wall.We study time-efficient solutions where time is measured using a standard notion of epochs – an epoch is a duration in which each robot completes at least one LCM cycle. For solutions to Doorway Egress with only 1 epoch, we: design an asynchronous algorithm if collisions are allowed; prove that an asynchronous algorithm is impossible if collisions are not allowed; and design a semi-synchronous algorithm without collisions. To further investigate asynchronous algorithms without collisions, we present algorithms with different combinations of robot abilities:•O(1) epochs with lights under obstructed visibility;•O(1) epochs without lights under unobstructed visibility; and•O(n) epochs without lights under obstructed visibility.Our results reveal dependencies and trade-offs among obstructed/unobstructed visibility, lights/no lights, and semi-synchronous/asynchronous settings.

We consider the distributed setting of$N$autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles following either the robots with lights model or the classical oblivious robots model. For the lights model, we assume obstructed visibility so that a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. In contrast, we assume unobstructed visibility in the classical model so that a robot sees all others irrespective of their positions. In addition, we consider a grid-based terrain embedded in the 2-dimensional Euclidean plane that restricts each robot's movement to one of the four neighboring grid points from its current position. This grid setting is a natural discretization of the 2-dimensional real plane and extends the robot swarm model in directions of greater applicability. The Arbitrary Pattern Formationproblem is to relocate the$N$robots (starting at arbitrary but distinct initial positions on a grid) to form an arbitrary target pattern given as input. In this paper, we provide two asynchronous algorithms for Arbitrary Pattern Formation, one on the lights model and another on the classical model. Key measures of the algorithms' performance include the time taken and the number of moves by each robot. Both algorithms run in$O(\max\{D^{i}, D^{p}\})$time with$O(\max\{D^{i}, D^{p}\})$moves by each robot, where$D^{i}$and$D^{p}$, respectively, are the diameters of the initial and pattern configurations. The algorithm for the lights model uses$O(1)$colors. We also prove a lower bound of$\Omega(\max\{D^{i}, D^{p}\})$for time for any Arbitrary Pattern Formationalgorithm if scaling is not allowed on the target pattern. Therefore, our algorithms are optimal w.r.t. time. Furthermore, our algorithms are also optimal w.r.t. the number of moves given the existing lower bound of$\Omega(\max\{D^{i}, D^{p}\})$on the number of moves. In sum, our results show that having lights provides a trade-off on the unobstructed visibility requirement in the classical model for Arbitrary Pattern Formation.

Recently, location-based social networks, that involve both social and spatial information, have received much attention in many real-world applications such as location-based services (LBS), map utilities, business planning, and so on. In this paper, we seamlessly integrate both social networks and spatial road networks, resulting in a so-calledspatial-social network, and study an important and novel query type, namedgroup planning query over spatial-social networks(GP-SSN), which is very useful for applications such as trip recommendations. In particular, a GP-SSN query retrieves a group of friends with common interests on social networks and a number of spatially closepoints of interest(POIs) on spatial road networks that best match group’s preferences and have the smallest traveling distances to the group. In order to tackle the GP-SSN problem, we design effective pruning methods, matching score pruning, user pruning, and distance pruning, to rule out false alarms of GP-SSN query answers and reduce the problem search space. We also propose effective indexing mechanisms to facilitate the GP-SSN query processing, and develop efficient GP-SSN query answering algorithms via index traversals. Extensive experiments have been conducted to evaluate the efficiency and effectiveness of our proposed GP-SSN query processing approaches.

We consider the distributed setting of$n$autonomous mobile robots that operate in Look-Compute-Move cycles and communicate with other robots using a constant number of colored lights (therobots with lightsmodel). We assume obstructed visibility where collinear robots do not see each other. In addition, we consider a grid-based terrain embedded in the 2-dimensional euclidean plane. TheConvex Hull Formationproblem is to relocate the$n$robots (starting at arbitrary, but distinct, initial positions) so that each robot is positioned on a vertex of a convex hull. In this article, we provide a framework for solvingConvex Hull Formation. We then provide four asynchronous algorithms under this framework. Key measures of the algorithms’ performance include the time taken and the space occupied. The presented algorithms are randomized and their time bounds hold with high probability. The first$O(\max \lbrace n^{2},D\rbrace)$-time,$O({n^{2}})$-perimeter, and$O({n^{3}})$-area algorithm serves to introduce key ideas, where$D$is the diameter of the initial configuration. The subsequent algorithms, differing in computational requirements, run in$O(\max \lbrace n^{\frac{3}{2}},D\rbrace)$time with a perimeter of$O(n^{\frac{3}{2}})$and area of$O(n^{3})$. We also prove lower bounds of$\Omega (n^{\frac{3}{2}})$for time and perimeter and$\Omega (n^{3})$for area, for anyConvex Hull Formationalgorithm; i.e., our$O(\max \lbrace n^{\frac{3}{2}},D\rbrace)-$time algorithm is optimal in time, perimeter, and area.

Flooding is a fundamental concept in distributed computing. In flooding, typically, a node forwards a message to its neighbors for the first time when it receives a message. Later if the node receives the same message again, it simply ignores the message and does not forward it. The nodes store a “message record” to ensure that the same message is not forwarded again. Hussak and Trehan introduced amnesiac flooding where nodes do not require to keep the message record. They established a surprising result that the amnesic flooding of a single (k = 1) message starting from some source node always terminates in bipartite graphs in e rounds and in non-bipartite graphs in [e + 1, e + D + 1] rounds, where e is the eccentricity of the source node and D is the diameter of the graph. Recently, Hussak and Trehan introduced dynamic amnesiac flooding initiated in possibly multiple rounds with possibly multiple (k > 1) messages from possibly multiple source nodes. They showed that the partial-send case where a node only sends a message to neighbours from which it did not receive any message in the previous round and the ranked full-send case where a node sends some highest ranked message to all neighbors from which it did not receive that message in the previous round, both terminate. However, they showed that the unranked full-send case, where a node sends some random message (not necessarily the highest ranked message) to all the neighbors from which it did not receive that message in the previous round, does not terminate. In this paper, we show that the unranked full-send case also terminates, provided that diameter D is known to graph nodes. We further show that the termination time is D · (2k − 1) rounds in bipartite graphs and (2D + 1) · (2k − 1) rounds in non-bipartite graphs.

Given an undirected, anonymous, port-labeled graph of $n$ memory-less nodes, $m$ edges, and degree $Δ$, we consider the problem of dispersing $k\leq n$ robots (or tokens) positioned initially arbitrarily on one or more nodes of the graph to exactly $k$ different nodes of the graph, one on each node. The objective is to simultaneously minimize time to achieve dispersion and memory requirement at each robot. If all $k$ robots are positioned initially on a single node, depth first search (DFS) traversal solves this problem in $O(\min\{m,kΔ\})$ time with $Θ(\log(k+Δ))$ bits at each robot. However, if robots are positioned initially on multiple nodes, the best previously known algorithm solves this problem in $O(\min\{m,kΔ\}\cdot \log \ell)$ time storing $Θ(\log(k+Δ))$ bits at each robot, where $\ell\leq k/2$ is the number of multiplicity nodes in the initial configuration. In this paper, we present a novel multi-source DFS traversal algorithm solving this problem in $O(\min\{m,kΔ\})$ time with $Θ(\log(k+Δ))$ bits at each robot, improving the time bound of the best previously known algorithm by $O(\log \ell)$ and matching asymptotically the single-source DFS traversal bounds. This is the first algorithm for dispersion that is optimal in both time and memory in arbitrary anonymous graphs of constant degree, $Δ=O(1)$. Furthermore, the result holds in both synchronous and asynchronous settings.

In this paper, we study the problem of shortest path planning for a mobile robot that does not possess unlimited energy for traveling. The robot can travel at most B distance with its battery fully charged. The objective of this energy-constrained robot is to travel from location S to location G in the presence of k charging stations while minimizing the incurred travel cost. As the robot is constrained by its energy, it needs to stop at one or more charging stations in order to recharge its battery. To solve the stated problem, we have proposed a variant of the classical A*search algorithm that plans the path of the robot in such a way that it moves as much distance as possible with a full recharge (the maximum being B). Furthermore, it chooses the one to be the next charging station that minimizes the extra distance that needs to be covered to reach it on top of the shortest distance from S to G. We have designed novel heuristic functions that guide the search towards such charging stations where the deviation from the shortest path without the constraint is the minimum. We prove that the proposed approach is complete. Results show that our proposed algorithm finds an optimal solution while taking a negligible time to execute.

The dispersion problem on graphs asks k ≤n robots placed initially arbitrarily on the nodes of an n-node anonymous graph to reposition autonomously to reach a configuration in which each robot is on a distinct node of the graph. This problem is of significant interest due to its relationship to other fundamental robot coordination problems, such as exploration, scattering, load balancing, and relocation of self-driving electric cars (robots) to recharge stations (nodes). The objective is to simultaneously minimize (or provide trade-off between) two fundamental performance metrics: (i) time to achieve dispersion and (ii) memory requirement at each robot. This problem has been relatively well-studied on static graphs. In this paper, we investigate it for the very first time on dynamic graphs. Particularly, we show that, even with unlimited memory at each robot and 1-neighborhood knowledge, dispersion is impossible to solve on dynamic graphs in the local communication model, where a robot can only communicate with other robots that are present at the same node. We then show that, even with unlimited memory at each robot but without 1-neighborhood knowledge, dispersion is impossible to solve in the global communication model, where a robot can communicate with any other robot in the graph possibly at different nodes. We then consider the global communication model with 1-neighborhood knowledge and establish a tight bound of Θ(k) on the time complexity of solving dispersion in any n-node arbitrary anonymous dynamic graph with Θ(log k) bits memory at each robot. Finally, we extend the fault-free algorithm to solve dispersion for (crash) faulty robots under the global model with 1-neighborhood knowledge.

We investigate scheduling algorithms for distributed transactional memory systems where transactions residing at nodes of a communication graph operate on shared, mobile objects. A transaction requests the objects it needs, executes once those objects have been assembled, and then sends the objects to other waiting transactions. We study scheduling algorithms with provable performance guarantees. Previously, only the offline batch scheduling setting was considered in the literature where transactions and the objects they access are known a priori. Minimizing execution time, even for the offline batch scheduling, is known to be NP-hard for arbitrary communication graphs. In this paper, we analyze for the very first time scheduling algorithms in the online dynamic scheduling setting where transactions and the objects they access are not known a priori and the transactions may arrive online over time. We provide efficient and near-optimal execution time schedules for dynamic scheduling in many specialized network architectures. The core of our technique is a method to convert offline schedules to online. We first describe a centralized scheduler which we then adapt it to a purely distributed scheduler. To our knowledge, these are the first attempts to obtain provably efficient online execution schedules for distributed transactional memory.

We consider the distributed setting of n autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and communicate with other robots using a constant number of colored lights (the robots with lights model). We assume obstructed visibility where a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. In addition, we consider a grid-based terrain embedded in the 2-dimensional Euclidean plane that restricts each robot movement to one of the four neighboring grid points from its current position. This grid setting is a natural discretization of the 2-dimensional real plane and extends the robot swarm model in directions of greater applicability. The CONVEX HULL FORMATION problem is to relocate the n robots (starting at arbitrary, but distinct, initial positions) so that each robot is positioned on a vertex of a convex hull. In this paper, we provide two asynchronous algorithms for CONVEX HULL FORMATION, both using a constant number of colors. Key measures of the algorithms' performance include the time taken and the space occupied (measured as the perimeter of the smallest rectangle enclosing the convex hull formed). The first O(max{n2, D})-time and O(n2)-perimeter algorithm serves to introduce key ideas, where D is the diameter of the initial 3 configuration. The second algorithm runs in O(max{n3/2, D}) 3 time with a perimeter of O(n3/2). We also prove lower bounds of Ω(n2/3) for both the time and perimeter for any CONVEX HULL FORMATION algorithm; that is, we establish our second algorithm as optimal in both time and perimeter.

We consider message-efficient continuous random sampling from a distributed stream, where the probability of inclusion of an item in the sample is proportional to a weight associated with the item. The unweighted version, where all weights are equal, is well studied, and admits tight upper and lower bounds on message complexity. For weighted sampling with replacement, there is a simple reduction to unweighted sampling with replacement. However, in many applications the stream may have only a few heavy items which may dominate a random sample when chosen with replacement. Weighted samplingwithout replacement (weighted SWOR) eludes this issue, since such heavy items can be sampled at most once. In this work, we present the first message-optimal algorithm for weighted SWOR from a distributed stream. Our algorithm also has optimal space and time complexity. As an application of our algorithm for weighted SWOR, we derive the first distributed streaming algorithms for trackingheavy hitters with residual error. Here the goal is to identify stream items that contribute significantly to the residual stream, once the heaviest items are removed. Residual heavy hitters generalize the notion of $\ell_1$ heavy hitters and are important in streams that have a skewed distribution of weights. In addition to the upper bound, we also provide a lower bound on the message complexity that is nearly tight up to a $łog(1/\eps)$ factor. Finally, we use our weighted sampling algorithm to improve the message complexity of distributed $L_1$ tracking, also known as count tracking, which is a widely studied problem in distributed streaming. We also derive a tight message lower bound, which closes the message complexity of this fundamental problem.

The coordination problems arising in a team of autonomous mobile robots have received a lot of attention in the distributed robotics community. Along those lines, we study in this paper the problem of coordinating autonomous mobile robots to reposition on a convex hull so that each robot sees all others. In particular, we consider non-transparent fat robots operating in the 2-dimensional plane. They are abstracted as unit discs and they make local decisions with vision being the only mean of coordination among them. We develop a (deterministic) distributed algorithm that solves the problem for a team of N ≥ 3 fat robots in O(N) time avoiding collisions under the semi-synchronous scheduler. The main idea is to enforce the robots to reach a configuration in which (i) the robots' centers form a convex hull; (ii) all robots are on the convex hull's boundary; and (iii) each robot can see all other robots. The result is achieved assuming some reasonable conditions on the input configuration and showing that starting from any input configuration that satisfies our conditions, robots reach such a configuration in linear time and terminate.

We consider the distributed setting of N autonomous mobile robots operating on graphs following Look-Compute-Move cycles and communicating with other robots using colored lights under the robots with lights model. We assume obstructed visibility under which a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. We introduce and study the fundamental problem of repositioning N robots on the nodes of a graph so that each robot has a path to all others without visiting an intermediate node that is occupied by any other robot (which we call the Complete Visitability problem). This problem is of interest due to its relationship to the problems of information collection, scattering, flocking, and dispersion on graphs. This problem generalizes the Complete Visitability problem studied in the literature, where the goal was to reposition the robots on a plane so that each robot sees all others. We have the following four results: We first show that it is impossible to solve Complete Visitability on arbitrary graphs, irrespective of the number of colors, time, and the robot activation setting (fully synchronous, semi-synchronous, or asynchronous). We then give an algorithm that solves Complete Visitability on grid graphs using 7 colors in the semi-synchronous setting. The algorithm uses 6 colors in the fully synchronous setting. The algorithm is collision-free. We then show that the total number of moves by any robot is O(h) and the runtime is O(h2) in our algorithm, where h denotes the number of layers of robots in the initial configuration. We also show that the number of moves bound is asymptotically tight and any Complete Visitability algorithm has runtime Ω(h) in grid graphs. We finally show that the algorithm and bounds for grid graphs extend to hexagonal tessellation graphs under chirality - robots agree on left and right directions.

We propose a scalable, cycle-collecting, decentralized, reference counting garbage collector with partial tracing. The algorithm is based on the Brownbridge system but uses four different types of references to label edges. Memory usage is O (log n) bits per node, where n is the number of nodes in the graph. The algorithm assumes an asynchronous network model with a reliable reordering channel. It collects garbage in O (E a ) time, where E a is the number of edges in the in- duced subgraph. The algorithm uses termination detection to manage the distributed computation, a unique identifier to break the symmetry among multiple collectors, and a transaction-based approach when multiple collectors conflict. Unlike existing algorithms, ours is not centralized, does not require barriers, does not require migration of nodes, does not require back-pointers on every edge, and is stable against concurrent mutation.

We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and communicate with other robots using colored lights (the robots with lights model). We study the fundamental problem of repositioning N autonomous robots on a plane sothat each robot is visible to all others (the Complete Visibility problem) on this model; a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. There exists an O(1) time, O(1) color algorithm for this problem in the semi-synchronous setting. In this paper, we provide the first O(log N) time, O(1) color algorithm for this problem in the asynchronous setting. This is a significant improvement over an O(N)-time translation of the semi-synchronous algorithm to the asynchronous setting. The proposed algorithm is collision-free - robots do not share positions and their paths do not cross.

We investigate scheduling algorithms for distributed transactional memory systems where transactions residing at nodes of a communication graph operate on shared, mobile objects. A transaction requests the objects it needs, executes once those objects have been assembled, and then possibly forwards those objects to other waiting transactions. Minimizing execution time in this model is known to be NP-hard for arbitrary communication graphs, and also hard to approximate within any factor smaller than the size of the graph. Nevertheless, networks on chips, multi-core systems, and clusters are not arbitrary. Here, we explore efficient execution schedules in specialized graphs likely to arise in practice: Clique, Line, Grid, Cluster, Hypercube, Butterfly, and Star. In most cases, when individual transactions request k objects, we obtain solutions close to a factor O(k) from optimal, yielding near-optimal solutions for constant k. These execution times approximate the TSP tour lengths of the objects in the graph. We show that for general networks, even for two objects (k=2), it is impossible to obtain execution time close to the objects' optimal TSP tour lengths, which is why it is useful to consider more realistic network models. To our knowledge, this is the first attempt to obtain provably fast schedules for distributed transactional memory.

We consider the distributed setting of $N$ autonomous mobile robots that operate in Look-Compute-Move cycles following the well-celebrated classic oblivious robots model. We study the fundamental problem where starting from an arbitrary initial configuration, N autonomous robots reposition themselves to a convex hull formation on the plane where each robot is visible to all others (the Complete Visibility problem). We assume obstructed visibility, where a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. We provide the first \cO(N) time algorithm for this problem in the fully synchronous setting. Our contribution is a significant improvement over the runtime of the only previously known algorithm for this problem which has a lower bound of \Omega(N^2). Our proposed algorithm is collision-free -- robots do not share positions and their paths do not cross.

We consider the fundamental problem of gathering a set of n robots in the Euclidean plane that have a physical extent and hence cannot share their positions with other robots. The objective is to determine a minimum time schedule to gather the robots as close together as possible around a predefined gathering point avoiding collisions. This problem with minimum time objective has applications in many real-world scenarios including fast autonomous coverage formation. Cord-Landwehr et al. (in Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science, 2011) gave a local greedy algorithm in a fully synchronous setting and proved that, for the discrete version of the problem where robots’ movements are restricted to the positions on an integral grid, their algorithm solves this problem in O ( nR ) rounds, where R is the distance from the farthest initial robot position to the gathering point. In this article, we improve significantly the round complexity of their algorithm to R + 2 · ( n - 1) rounds. This round complexity is obtained in the following modified model: (1) the viewing range of the robots is increased to three hops and (2) robots can additionally move to the diagonally opposite corner to a grid cell in one step—that is, they can traverse the two corresponding grid edges in one time step. We also prove that there are initial configurations of n robots in this problem where at least R +(n-1)/2 rounds are needed by any local greedy algorithm. Furthermore, we improve the lower bound to R + ( n - 1) rounds for the algorithm of Cord-Landwehr et al. These results altogether provide a tight runtime analysis of their algorithm.

We consider the group-communication maintenance problem between a set ofkmobile agents that are tracked by a static sensor network. We develop a scalable deterministic distributed algorithm for maintaining a Steiner tree of the agents so that group communication between them can be provided with the minimum total cost possible. The main idea is that our algorithm maintains a virtual tree of mobile agents that can be immediately converted to an actual Steiner tree at all times. Our algorithm achieves the Steiner tree with total length at mostO(logk) times the length of the optimal Steiner tree in the constant-doubling graph model. The total communication cost (the number of messages) to maintain the Steiner tree is onlyO(min{logn, logD}) times the optimal communication cost, wherenandD, respectively, are the number of nodes and the diameter of the constant-doubling network. We also develop improved algorithms for the mobilek-center, sparse-aggregation, and distributed-matching problems. Experimental evaluation results show the benefits of our algorithms compared to previous algorithms. These four problems are NP-hard and, to the best of our knowledge, our algorithms are the first near-optimal deterministic algorithms for maintaining approximate solutions to these important network problems with low maintenance costs in a distributed setting.

We consider the self-deployment problem in mobile sensor networks with the objective of providing focused coverage for a point of interest (POI) such that the maximum area around it is covered by sensors without sensing holes. We present a local greedy algorithm, called TTGREEDY, that solves this problem in at most R + 2.(n-1) time steps, where R is the distance to the farthest initial sensor position from the POI and n is the number of sensors. This is a significant improvement over the best previously known O(D) time step algorithm of Blazovics and Lukovszki, where D is the sum of the initial distances to the sensors from the POI. The main idea is to synchronously drive mobile sensors along a locally-computed triangle tessellation avoiding collisions of sensors. We also show that there are initial configurations of n sensors in this problem where at least R + (n-1)/2 time steps are needed by any greedy algorithm. These results provide the first tight runtime (within a small constant factor) solution to this problem.

We consider the problem of repositioning N autonomous robots on a plane so that each robot is visible to all others (the Complete Visibility problem), a robot cannot see another robot if there is a third robot positioned between them on the straight line joining them. Robots communicate using collared lights. The computation is synchronous and each robot performs a look-compute-move during a round. Specifically, during a round a robot is permitted to observe the light and position of every robot visible to it. It may also perform an internal computation based on the observed lights and positions(including deciding on a new-collar for its own light), and possibly moving to a new position at the end of the round. The challenge posed by this model of computation stems from the fact that each robot has only a constant number of colours for its lights(symbols for communication) and no memory(except for the persistence of lights) between rounds. In this paper we first show that the best previously known algorithm for the complete visibility problem on this model runs in linear time in the worst case. We then present the first logarithmic time complexity algorithm for Complete Visibility. The model we assume use sterility, is fully-synchronous and allows robot paths to cross.

We consider the fundamental problem of gathering a set of n robots in the Euclidean plane which have a physical extent and hence they cannot share their positions with other robots. The objective is to determine a minimum time schedule to gather the robots as close together as possible around a predefined gathering point avoiding collisions. This problem has applications in many real world scenarios including fast autonomous coverage formation. Cord-Landwehr et al. (SOFSEM 2011) gave a local greedy algorithm in a synchronous setting and proved that, for the discrete version of the problem where robots movements are restricted to the positions on an integral grid, their algorithm solves this problem in O(nR) rounds, where R is the distance from the farthest initial robot position to the gathering point. In this paper, we improve significantly the round complexity of their algorithm to R + 2 · (n - 1) rounds. We also prove that there are initial configurations of n robots in this problem where at least R + (n - 1) over 2 rounds are needed by any local greedy algorithm. Furthermore, we improve the lower bound to R + (n - 1) rounds for the algorithm of Cord-Landwehr et al.. These results altogether provide a tight runtime analysis of their algorithm.

We consider scheduling problems in the data flow model of distributed transactional memory. Objects shared by transactions move from one network node to another by following network paths. We examine how the objects' transfer in the network affects the completion time of all transactions and the total communication cost. We show that there are problem instances for which there is no scheduling algorithm that can simultaneously minimize the completion time and communication cost. These instances reveal a trade-off, minimizing execution time implies high communication cost and vice versa. On the positive side, we provide scheduling algorithms which are independently communication cost near-optimal or execution time efficient.

We consider the group communication maintenance problem between a set of k mobile agents that are tracked by a static sensor network. We develop a scalable deterministic distributed algorithm for maintaining a Steiner tree of the agents so that group communication between them can be provided in the minimum cost possible. The main idea is that our algorithm maintains a virtual tree of mobile agents which can be immediately converted to an actual Steiner tree at all times. Our algorithm achieves the Steiner tree with total length at most O (log k) times the length of the minimum Steiner tree in the constant-doubling graph model. The total communication cost (messages) to maintain the Steiner tree is only O (min {log n, log D}) times the optimal communication cost, where n and D, respectively, are the number of nodes and the diameter of the network. We also develop improved algorithms for the k-center, sparse aggregation, and distributed matching problems. Experimental evaluation results show the benefits of our algorithms compared to previous algorithms. These four problems are NP-hard and, to the best of our knowledge, our algorithms are the first near-optimal deterministic algorithms for maintaining approximate solutions to these problems with low maintenance costs in a distributed setting.

This paper presents a new concurrent garbage collection algorithm based on two types of reference, strong and weak, to link the graph of objects. Strong references connect the roots to all the nodes in the graph but do not contain cycles. Weak references may, however, contain cycles.

We consider the problem of implementing transactional memory in large-scale distributed networked systems. We present and analyze Spiral, a novel distributed directory-based protocol for transactional memory. Spiral is designed for the data-flow distributed implementation of software transactional memory which supports three basic operations: publish, allowing a shared object to be inserted in the directory so that other nodes can find it; lookup, providing a read-only copy of the object to the requesting node; move, allowing the requesting node to write the object locally after the node gets it. The protocol runs on a hierarchical directory construction based on sparse covers, where clusters at each level are ordered to avoid race conditions while serving concurrent requests. Given a shared object the protocol maintains a directory path pointing to the object. The basic idea is to use “spiral” paths that grow outward to search for the directory path of the object in a bottom-up fashion. For general networks, this protocol guarantees an O(log2n · log D) approximation for move requests, where n is the number of nodes and D is the diameter of the network. It also guarantees polylog approximation for lookup requests. To the best of our knowledge, this is the first consistency protocol for distributed transactional memory that achieves poly-log approximation in general networks.