S. Guilbault, A. Pelc, Gathering asynchronous oblivious agents with local vision in regular bipartite graphs, Theoretical Computer Science 509 (2013), 86-96.
S. Guilbault, A. Pelc, Gathering asynchronous oblivious agents with local vision in regular bipartite graphs, Theoretical Computer Science 509 (2013), 86-96.
Preliminary version appeared in:
Proc. 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2011), June 2011, Gdansk, Poland, LNCS 6796, 162-173.
Abstract:
We consider the problem of gathering identical, memoryless, mobile agents in one node of an anonymous graph. Agents start from different nodes of the graph. They operate in Look-Compute-Move cycles and have to end up in the same node. In one cycle, an agent takes a snapshot of its immediate neighborhood (Look), makes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each agent. The novelty of our model with respect to the existing literature on gathering asynchronous oblivious agents in graphs is that the agents have very restricted perception capabilities: they can only see their immediate neighborhood. An initial configuration of agents is called gatherable if there exists an algorithm that gathers all the agents of the configuration in one node and keeps them idle from then on, regardless of the actions of the asynchronous adversary. (The algorithm can be even tailored to gather this specific configuration.) The gathering problem is to determine which configurations are gatherable and find a (universal) algorithm which gathers all gatherable configurations. We give a complete solution of the gathering problem for regular bipartite graphs. Our main contribution is the proof that the class of gatherable initial configurations is very small: it consists only of ``stars'' (an agent A with all other agents adjacent to it) of size at least 3. On the positive side we give an algorithm accomplishing gathering for every gatherable configuration.
D. Kowalski, A. Pelc, Leader election in ad hoc radio networks: a keen ear helps, Journal of Computer and System Sciences 79 (2013), 1164-1180.
Preliminary version appeared in:
Proc. 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), July 2009, Rhodes, Greece, LNCS 5556, 521-533.
Abstract:
We address the fundamental distributed problem of leader election in ad hoc radio networks modeled as undirected graphs. Nodes are stations having distinct integer labels, and each node knows only its own label and a polynomial upper bound on all labels. A signal from a transmitting node reaches all neighbors. What distinguishes radio networks from message-passing networks is that a message is received successfully by a node, if and only if exactly one of its neighbors transmits in this round. If two neighbors of a node transmit simultaneously in a given round, none of the messages is heard by the receiving node. In this case we say that a collision occurred at this node. An important capability of nodes of a radio network is collision detection: the ability of nodes to distinguish a collision from the background noise occurring when no neighbor transmits. (This ability is the ``keen ear'' of the nodes.) Can collision detection speed up leader election in arbitrary radio networks? We give a positive answer to this question. More precisely, our main result is a deterministic leader election algorithm working in time O(n) in all n-node networks, if collision detection is available, while it is known that deterministic leader election requires time Omega (n log n), even for complete networks, if there is no collision detection. This is the first computational task whose execution for arbitrary radio networks is shown to be faster with collision detection than without it.
P. Fraigniaud, A. Pelc, Delays induce an exponential memory gap for rendezvous in trees, ACM Transactions on Algorithms 9 (2013), article 17.
Preliminary version appeared as:
P. Fraigniaud, A. Pelc, Deterministic rendezvous in trees with little memory, Proc. 22nd International Symposium on Distributed Computing (DISC 2008), Septembre 2008, Arcachon, France, LNCS 5218, 242-256.
and
P. Fraigniaud, A. Pelc, Delays induce an exponential memory gap for rendezvous in trees, Proc. 22nd Ann. ACM Symposium on Parallel Algorithms and Architectures (SPAA 2010), June 2010, Santorini, Greece, 224-232.
Abstract:
The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. In this paper, we focus on rendezvous in trees, and, analogously to the efforts that have been made for solving the exploration problem with compact automata, we study the size of memory of mobile agents that permits to solve the rendezvous problem deterministically. We assume that the agents are identical, and move in synchronous rounds. We first show that if the delay between the starting times of the agents is arbitrary, then the lower bound on memory required for rendezvous is Omega(log n) bits, even for the line of length n. This lower bound meets a previously known upper bound of O(log n) bits for rendezvous in arbitrary graphs of size at most $n$. Our main result is a proof that the amount of memory needed for rendezvous with simultaneous start depends essentially on the number l of leaves of the tree, and is exponentially less impacted by the number n of nodes. Indeed, we present two identical agents with O(log l + log log n) bits of memory that solve the rendezvous problem in all trees with at most n nodes and at most l leaves. Hence, for the class of trees with polylogarithmically many leaves, there is an exponential gap in minimum memory size needed for rendezvous between the scenario with arbitrary delay and the scenario with delay zero. Moreover, we show that our upper bound is optimal by proving that Omega(log l + log log n) bits of memory are required for rendezvous, even in the class of trees with degrees bounded by 3.
J. Czyzowicz, D. Ilcinkas, A. Labourel, A. Pelc, Worst-case optimal exploration of terrains with obstacles, Information and Computation 225 (2013), 16-28.
Preliminary version appeared in:
Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010), June 2010, Bergen, Norway, LNCS 6139, 1-12.
Abstract:
A mobile robot represented by a point moving in the plane has to explore an unknown flat terrain with impassable obstacles. Both the terrain and the obstacles are modeled as arbitrary polygons. We consider two scenarios: the unlimited vision, when the robot situated at a point p of the terrain explores (sees) all points q of the terrain for which the segment pq belongs to the terrain, and the limited vision, when we require additionally that the distance between p and q be at most 1. All points of the terrain (except obstacles) have to be explored and the performance of an exploration algorithm, called its complexity, is measured by the length of the trajectory of the robot. For unlimited vision we show an exploration algorithm with complexity O(P+D\sqrt{k}), where P is the total perimeter of the terrain (including perimeters of obstacles), D is the diameter of the convex hull of the terrain, and k is the number of obstacles. We do not assume knowledge of these parameters. We also prove a matching lower bound showing that the above complexity is optimal, even if the terrain is known to the robot. For limited vision we show exploration algorithms with complexity O(P+A+\sqrt{Ak}), where A is the area of the terrain (excluding obstacles). Our algorithms work either for arbitrary terrains, if one of the parameters A or k is known, or for c-fat terrains, where c is any constant (unknown to the robot) and no additional knowledge is assumed. We also prove a matching lower bound Omega(P+A+\sqrt{Ak}) on the complexity of exploration for limited vision, even if the terrain is known to the robot.
P. Flocchini, D. Ilcinkas, A. Pelc, N. Santoro, Computing without communicating: Ring exploration by asynchronous oblivious robots, Algorithmica 65 (2013), 562-583.
Preliminary version appeared in:
Proc. 11th International Conference on Principles of Distributed Systems (OPODIS 2007), December 2007, Guadeloupe, LNCS 4878, 105-118.
Abstract:
We consider the problem of exploring an anonymous unoriented ring by a team of k identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This weak scenario is standard when the spatial universe in which the robots operate is the two-dimensional plane, but (with one exception) has not been investigated before for networks. Our results imply that, although these weak capabilities of robots render the problem considerably more difficult, ring exploration by a small team of robots is still possible. We first show that, when k and n are not co-prime, the problem is not solvable in general, e.g., if k divides n there are initial placements of the robots for which gathering is impossible. We then prove that the problem is always solvable provided that n and k are co-prime, by giving an exploration algorithm that always terminates, starting from arbitrary initial configurations. Finally, we consider the minimum number rho(n) of robots that can explore a ring of size n. As a consequence of our positive result we show that rho(n) is O(log n). We additionally prove that Omega(log n) robots are necessary for infinitely many n.
J. Czyzowicz, A. Kosowski, A. Pelc, Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains, Theory of Computing Systems 52 (2013), 179-199.
Preliminary version appeared in:
Proc. 35th International Symposiums on Mathematical Foundations of Computer Science (MFCS 2010), August 2010, Brno, Czech Republic, LNCS 6281, 294-305.
Abstract:
Two mobile agents, modeled as points starting at different locations of an unknown terrain, have to meet. The terrain is a polygon with polygonal holes. We consider two versions of this rendezvous problem: exact RV, when the points representing the agents have to coincide at some time, and eps-RV, when these points have to get at distance less than eps in the terrain. In any terrain, each agent chooses its trajectory, but the movements of the agent on this trajectory are controlled by an adversary that may, e.g., speed up or slow down the agent. Agents have bounded memory: their computational power is that of finite state machines. Our aim is to compare the feasibility of exact and of eps-RV when agents are anonymous vs. when they are labeled. We show classes of polygonal terrains which distinguish all the studied scenarios from the point of view of feasibility of rendezvous. The features which influence the feasibility of rendezvous include symmetries present in the terrains, boundedness of their diameter, and the number of vertices of polygons in the terrains.
S. Guilbault, A. Pelc, Gathering asynchronous oblivious agents with restricted vision in an infinite line, Proc. 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2013), November 2013, Osaka, Japan, LNCS 8255, 296-310.
Abstract:
We consider the problem of gathering identical, memoryless, mobile agents in one node of an infinite anonymous line of nodes. Agents start from different nodes of the line. They operate in Look-Compute-Move cycles and have to end up at the same node. Our model differs from most of the existing literature on gathering asynchronous oblivious agents in graphs in that the agents have restricted perception capabilities: they can only see at bounded distance d (called the radius of vision) from their current location. In one cycle, an agent takes a snapshot of the part of the line at distance at most d from it (Look), makes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each agent. An initial configuration of agents is called gatherable if there exists an algorithm that gathers all the agents of the configuration in one node and keeps them idle from then on, regardless of the actions of the asynchronous adversary. (The algorithm can be even tailored to gather this specific configuration.) A gathering algorithm is universal if it gathers all gatherable configurations. We observe that if the vision of agents is unrestricted then a universal gathering algorithm exists. For radius of vision d=1 a universal gathering algorithm is known. By contrast, our main result shows that for radius of vision d>1 there is no universal gathering algorithm. Our result remains valid for rings of size at least 7d+8.