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 *A*is
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.