E.G. Fusco, A. Pelc, Acknowledged broadcasting in ad hoc radio networks,
Information Processing Letters 109 (2008), 136-141.
E.G. Fusco, A. Pelc, Acknowledged broadcasting in ad hoc radio networks,
Information Processing Letters 109 (2008), 136-141.
Abstract:
We consider ad hoc radio networks in which each node knows only its own identity but is unaware of the topology of the network, or of any bound on its size or diameter. Acknowledged broadcasting (AB) is a communication task consisting in transmitting a message from a distinguished {\em source} to all other nodes of the network and making this fact common knowledge among all nodes. To do this, the underlying directed graph must be strongly connected. Working in a model allowing all nodes to transmit spontaneously even before getting the source message, Chlebus et al. proved that AB is impossible, if collision detection is not available, and gave an AB algorithm using collision detection that works in time O(nD) where $n$ is the number of nodes and D is the eccentricity of the source. Uchida et al. showed an AB algorithm without collision detection working in time O(n^{4/3} log ^{10/3} n) for all strongly connected networks of size at least 2. We improve those two results by showing AB algorithms that have the same complexity as the best known broadcasting algorithms without acknowledgement, both with and without collision detection. More precisely, our AB algorithm with collision detection works in time O(n log^2 D), for arbitrary strongly connected networks, and our AB algorithm without collision detection works in time O(n log n loglog n) for all strongly connected networks of size n>1. Moreover, we show that in the model in which only nodes that already got the source message can transmit, AB is infeasible in a strong sense: for any AB algorithm there exist arbitrarily large networks for which this algorithm is incorrect.
P. Fraigniaud, D. Ilcinkas, A. Pelc, Tree exploration with advice,
Information and Computation 206 (2008), 1276-1287.
Preliminary version appeared in:
Proc. 31st International Symposium on Mathematical Foundations of Computer Science, (MFCS 2006), August/September 2006, Stara Lesna, Slovakia, LNCS 4162, 24-37.
Abstract:
We study the amount of knowledge about the network that is required in order to efficiently solve a task concerning this network. The impact of available information on the efficiency of solving network problems, such as communication or exploration, has been investigated before but assumptions concerned availability of particular items of information about the network, such as the size, the diameter, or a map of the network. In contrast, our approach is quantitative: we investigate the minimum number of bits of information (bits of advice) that has to be given to an algorithm in order to perform a task with given efficiency. We illustrate this quantitative approach to available knowledge by the task of tree exploration. A mobile entity (robot) has to traverse all edges of an unknown tree, using as few edge traversals as possible. The quality of an exploration algorithm Ais measured by its competitive ratio, i.e., by comparing its cost (number of edge traversals) to the length of the shortest path containing all edges of the tree. Depth-First-Search has competitive ratio 2 and, in the absence of any information about the tree, no algorithm can beat this value. We determine the minimum number of bits of advice that has to be given to an exploration algorithm in order to achieve competitive ratio strictly smaller than 2. Our main result establishes an exact threshold number of bits of advice that turns out to be roughly log log D, where D is the diameter of the tree. More precisely, for any constant c, we construct an exploration algorithm with competitive ratio smaller than 2, using at most log log D -c bits of advice, and we show that every algorithm using log log D -g(D) bits of advice, for any function g unbounded from above, has competitive ratio at least 2.
P. Fraigniaud, D. Ilcinkas, A. Pelc, Impact of memory size on graph exploration capability,
Discrete Applied Mathematics 156 (2008), 2310-2319.
Abstract:
A mobile agent (robot), modeled as a finite automaton, has to visit all nodes of a regular graph. How does the memory size of the agent (the number of states of the automaton) influence its exploration capability? In particular, does every increase of the memory size enable an agent to explore more graphs? We give a partial answer to this problem by showing that a strict gain of the exploration power can be obtained by a polynomial increase of the number of states. We also show that, for automata with few states, the increase of memory by even one state results in the capability of exploring more graphs.
R. Klasing, E. Markou, A. Pelc, Gathering asynchronous oblivious mobile robots in a ring,
Theoretical Computer Science 390 (2008), 27-39.
Preliminary version appeared in:
Proc. 17th International Symposium on Algorithms and Computation (ISAAC 2006), December 2006, Kolkata, India, LNCS 4288, 744-753.
Abstract:
We consider the problem of gathering identical, memoryless, mobile robots in one node of an anonymous unoriented ring. Robots start from different nodes of the ring. They operate in Look-Compute-Move cycles and have to end up in the same node. In one cycle, a robot takes a snapshot of the current configuration (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 robot. For an odd number of robots we prove that gathering is feasible if and only if the initial configuration is not periodic, and we provide a gathering algorithm for any such configuration. For an even number of robots we decide feasibility of gathering except for one type of symmetric initial configurations, and provide gathering algorithms for initial configurations proved to be gatherable.
D. Ilcinkas, A. Pelc, Impact of asynchrony on the behavior of rational selfish agents,
Fundamenta Informaticae 82 (2008), 113-125.
Abstract:
The behavior of rational selfish agents has been classically studied in the framework of strategic games in which each player has a set of possible actions, players choose actions simultaneously and the payoff for each player is determined by the matrix of the game. However, in many applications, players choose actions asynchronously, and simultaneity of this process is not guaranteed: it is possible that a player learns the action of another player before making its choice. Delays of choices are controled by the adversary and each player can only secure the worst-case payoff over the adversary's decisions. In this paper we consider such asynchronous versions of arbitrary two-person strategic games and we study how the presence of the asynchronous adversary influences the behavior of the players, assumed to be selfish but rational. We concentrate on deterministic (pure) strategies, and in particular, on the existence and characteristics of pure Nash equilibria in such games. It turns out that the rational behavior of players changes significantly if the decision process is asynchronous. We show that pure Nash equilibria often exist in the asynchronous version of the game even if there were no such equilibria in the synchronous game. We also show that a mere threat of asynchrony in the game may make social optimum a rational choice while it was not rational in the synchronous game.
T. Calamoneri, E. G. Fusco, A. Pelc, Impact of information on the complexity of asynchronous radio broadcasting, Proc. 12th International Conference on Principles of Distributed Systems (OPODIS 2008), December 2008, Luxor, Egypt, LNCS 5401, 311-330.
Abstract:
We consider asynchronous deterministic broadcasting in radio networks. An execution of a broadcasting protocol is a series of events, each of which consists of simultaneous transmitting or delivering of messages. The aim is to transmit the source message to all nodes of the network. If two messages are delivered simultaneously to a node, a collision occurs and this node does not hear anything. An asynchronous adversary may delay message deliveries, so as to create unwanted collisions and interfere with message dissemination. The total number of message transmissions executed by a protocol in the worst case is called the work of the protocol, and is used as the measure of its complexity. The aim of this paper is to study how various types of information available to nodes influence the optimal work of an asynchronous broadcasting protocol. This information may concern past events possibly affecting the behavior of nodes (adaptive vs. oblivious protocols), or may concern the topology of the network or some of its parameters. We show that decreasing the knowledge available to nodes may cause exponential increase of work of an asynchronous broadcasting protocol, and in some cases may even make broadcasting impossible.