E. Fusco, A. Pelc, How much memory is needed for leader election, Distributed Computing 24 (2011), 65-78.
E. Fusco, A. Pelc, How much memory is needed for leader election, Distributed Computing 24 (2011), 65-78.
Preliminary version appeared in:
Proc. 24th International Symposium on Distributed Computing (DISC 2010), September 2010, Boston, U.S.A., LNCS 6343, 251-266.
Abstract:
We study the minimum memory size with which nodes of a network have to be equipped, in order to solve deterministically the leader election problem. Nodes are unlabeled, but ports at each node have arbitrary fixed labelings which, together with the topology of the network, can create asymmetries to be exploited in leader election. We consider two versions of the leader election problem: strong LE in which exactly one leader has to be elected, if this is possible, while all nodes must terminate in a state ``infeasible'' when the election of a unique leader fails, and weak LE, which differs from strong LE in that no requirement on the behavior of nodes is imposed, if leader election is impossible. Nodes are modeled as identical automata and we ask what is the minimum amount of memory of such an automaton to enable leader election. We show that logarithmic memory is optimal for both strong and weak leader election in the class of arbitrary connected graphs. By contrast we show that strong LE can be accomplished in the class of trees of maximum degree Delta using only O(log log Delta) bits of memory, thus proving an exponential gap in memory requirements for leader election between the class of trees and the class of arbitrary graphs.
J. Czyzowicz, D. Ilcinkas, A. Labourel, A. Pelc, Asynchronous deterministic rendezvous in bounded terrains, Theoretical Computer Science 412 (2011), 6926-6937.
Preliminary version appeared in:
Proc. 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2010), June 2010, Sirince, Turkey, LNCS 6058, 72-85.
Abstract:
Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Agents are modeled as points, and each of them is equipped with a compass. Compasses of agents may be incoherent. Agents construct their routes, but the actual walk of each agent is decided by the adversary: the movement of the agent can be at arbitrary speed, the agent may sometimes stop or go back and forth, as long as the walk of the agent in each segment of its route is continuous, does not leave it and covers all of it. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both agents agree, or not, (3) agents have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the agents' trajectories until their meeting. For each scenario we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight.
P. Flocchini, D. Ilcinkas, A. Pelc, N. Santoro, How many oblivious robots can explore a line, Information Processing Letters 111 (2011), 1027-1031.
Abstract:
We consider the problem of exploring an anonymous line by a team of k identical, oblivious, asynchronous deterministic mobile robots that can view the environment but cannot communicate. We completely characterize sizes of teams of robots capable of exploring a n-node line.
J. Czyzowicz, L. Gasieniec, D. Kowalski, A. Pelc, Consensus and mutual exclusion in a multiple access channel, IEEE Transactions on Parallel and Distributed Systems 22 (2011), 1092-1104.
Preliminary version appeared in:
Proc. 23rd International Symposium on Distributed Computing (DISC 2009), September 2009, Elche, Spain, LNCS 5805, 512-526.
Abstract:
We consider deterministic feasibility and time complexity of two fundamental tasks in distributed computing: consensus and mutual exclusion. Processes have different labels and communicate through a multiple access channel. The adversary wakes up some processes in possibly different rounds. In any round every awake process either listens or transmits. The message of a process i is heard by all other awake processes, if i is the only process to transmit in a given round. If %many processes transmit more than one process transmits simultaneously, there is a collision and no message is heard. We consider three characteristics that may or may not exist in the channel: collision detection (listening processes can distinguish collision from silence), the availablity of a global clock showing the round number, and the knowledge of the number n of all processes. If none of the above three characteristics is available in the channel, we prove that consensus and mutual exclusion are infeasible; if at least one of them is available, both tasks are feasible and we study their time complexity. Collision detection is shown to cause an exponential gap in complexity: if it is available, both tasks can be performed in time logarithmic in n, which is optimal, and without collision detection both tasks require linear time. We then investigate both consensus and mutual exclusion in the absence of collision detection, but under alternative presence of the two other features. With global clock, we give an algorithm whose time complexity linearly depends on n and on the wake-up time, and an algorithm whose complexity does not depend on the wake-up time and differs from the linear lower bound only by a factor O(log^2 n). If n is known, we also show an algorithm whose complexity differs from the linear lower bound only by a factor O(log^2 n).
E. Fusco, A. Pelc, Trade-offs between the size of advice and broadcasting time in trees, Algorithmica 60 (2011), 719-734.
Preliminary version appeared in:
Proc. 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2008), June 2008, Munich, Germany, 77-84.
Abstract:
We study the problem of the amount of information required to perform fast broadcasting in tree networks. The source located at the root of the tree has to disseminate a message to all nodes. In each round each informed node can transmit to one child. Nodes do not know the topology of the tree but an oracle knowing it can give a string of bits of advice to the source which can then pass it down the tree with the source message. The quality of a broadcasting algorithm with advice is measured by its competitive ratio: the worst case ratio taken over n-node trees, between the time of this algorithm and the optimal broadcasting time in the given tree. Our goal is to find a trade-off between the size of advice and the best competitive ratio of a broadcasting algorithm for n-node trees. We establish such a trade-off with an approximation factor of O(n^eps), for an arbitrarily small positive constant eps. This is the first problem for which a trade-off between the amount of provided information and the efficiency of the solution is shown for arbitrary size of advice.
C. Ambuehl, L. Gasieniec, A. Pelc, T. Radzik, X. Zhang, Tree exploration with logarithmic memory, ACM Transactions on Algorithms 7 (2011), article 17.
Preliminary version appeared as:
L. Gasieniec, A. Pelc, T. Radzik, X. Zhang, Tree exploration with logarithmic memory, Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), January 2007, New Orleans, Louisiana, USA, 585-594.
Abstract:
We consider the task of network exploration by a mobile agent (robot) with small memory. The agent has to traverse all nodes and edges of a network (represented as an undirected connected graph), and return to the starting node. Nodes of the network are unlabeled and edge ports are locally labeled at each node. The agent has no a priori knowledge of the topology of the network or of its size, and cannot mark nodes in any way. Under such weak assumptions, cycles in the network may prevent feasibility of exploration, hence we restrict attention to trees. We present an algorithm to accomplish tree exploration (with return) using O(log n)-bit memory for all n-node trees. This matches a known lower bound. We also extend our O(log n)-bit memory traversal mechanism to a weaker model in which ports at each node are ordered in circular manner, however the explicit values of port numbers are not available.
J. Czyzowicz, A. Labourel, A. Pelc, Optimality and competitiveness of exploring polygons by mobile robots, Information and Computation 209 (2011), 74-88.
Preliminary version appeared in:
Proc. 17th European Symposium on Algorithms (ESA 2009), September 2009, Copenhagen, Denmark, LNCS 5757, 263-274.
Abstract:
A mobile robot, represented by a point moving along a polygonal line in the plane, has to explore an unknown polygon and return to the starting point. The robot has a sensing area which can be a circle or a square centered at the robot. This area shifts while the robot moves inside the polygon, and at each point of its trajectory the robot ``sees'' (explores) all points for which the segment between the robot and the point is contained in the polygon and in the sensing area. We focus on two tasks: exploring the entire polygon and exploring only its boundary. We consider several scenarios: both shapes of the sensing area and the Manhattan and the Euclidean metrics. We focus on two quality benchmarks for exploration performance: optimality (the length of the trajectory of the robot is equal to that of the optimal robot knowing the polygon) and competitiveness (the length of the trajectory of the robot is at most a constant multiple of that of the optimal robot knowing the polygon). Most of our results concern rectilinear polygons. We show that optimal exploration is possible in only one scenario, that of exploring the boundary by a robot with square sensing area, starting at the boundary and using the Manhattan metric. For this case we give an optimal exploration algorithm, and in all other scenarios we prove impossibility of optimal exploration. For competitiveness the situation is more optimistic: we show a competitive exploration algorithm for rectilinear polygons whenever the sensing area is a square, for both tasks, regardless of the metric and of the starting point. Finally, we show a competitive exploration algorithm for arbitrary convex polygons, for both shapes of the sensing area, regardless of the metric and of the starting point.
S. Guilbault, A. Pelc, Asynchronous rendezvous of anonymous agents in arbitrary graphs, Proc. 15th International Conference on Principles of Distributed Systems (OPODIS 2011), December 2011, Toulouse, France, LNCS 7109, 162-173.
Abstract:
Two identical (anonymous) mobile agents have to meet in an arbitrary, possibly infinite, unknown connected graph. Agents are modeled as points, they start at nodes of the graph chosen by the adversary and the route of each of them only depends on the already traversed portion of the graph and, in the case of randomized rendezvous, on the result of coin tossing. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent in each segment of its route is continuous, does not leave it and covers all of it. Meeting means that both agents must be at the same time in some node or in some point inside an edge of the graph. In the deterministic scenario we characterize the initial positions of the agents for which rendezvous is feasible and we provide an algorithm guaranteeing asynchronous rendezvous from all such positions in an arbitrary connected graph. In the randomized scenario we show an algorithm that achieves asynchronous rendezvous with probability 1, for arbitrary initial positions in an arbitrary connected graph. In both cases the graph may be finite or (countably) infinite.
A. Pelc, DISC 2011 Invited Lecture: Deterministic rendezvous in networks: Survey of models and results, Proc. 25th International Symposium on Distributed Computing (DISC 2011), September 2011, Rome, Italy, LNCS 6950, 1-15.
Abstract:
Two or more mobile entities, called {\em agents} or {\em robots}, starting at distinct initial positions in some environment, have to meet. This task is known in the literature as {\em rendezvous}. Among many alternative assumptions that have been used to study the rendezvous problem, two most significantly influence the methodology appropriate for its solution. The first of these assumptions concerns the environment in which the mobile entities navigate: it can be either a terrain in the plane, or a network modeled as an undirected graph. In the case of networks, methods and results further depend on whether the agents have the ability to mark nodes in some way. The second assumption concerns the way in which the entities move: it can be either deterministic or randomized. In this paper we survey models and results concerning deterministic rendezvous in networks, where agents cannot mark nodes.