A. Pelc, K.J. Pelc, Same game, new tricks: what makes a good strategy in the Prisoner's Dilemma?,
*Journal of Conflict Resolution* 53 (2009), 774-793.

Abstract:

The aim of this paper is to distinguish between strategies in the Iterated Prisoner's Dilemma
on the basis of their relative performance in a given population set.
We first define a natural order on such strategies which disregards isolated disturbances,
by using the limit of time-average payoffs.
This order allows us to consider one strategy as strictly better than another in some population of strategies.
We then determine a strategy *sigma* to be ``robust", if in any population consisting of copies
of two types of strategies,
$\sigma$ itself and some other strategy *tau*, the strategy *sigma* is never worse than *tau*.
We present a large class of such robust strategies. Strikingly, robustness can accommodate an arbitrary level
of generosity, conditional on the strength of subsequent retaliation; and it does not require symmetric
retaliation. Taken together, these findings allow us to design strategies that significantly lessen the problem of noise,
without forsaking performance. Finally, we show that no strategy
exhibits robustness in all population sets of three or more strategy types.

P. Fraigniaud, C. Gavoille, D. Ilcinkas, A. Pelc,
Distributed computing with advice: information sensitivity of graph coloring, *Distributed Computing* 21 (2009), 395-403.

Preliminary version appeared in:

Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), July 2007, Wroclaw, Poland, LNCS 4596, 231-242.

Abstract:

We study the problem of the amount of information (advice) about a graph that must be given to its nodes in order to achieve fast distributed computations. The required size of the advice enables to measure the information sensitivity of a network problem. A problem is information sensitive if little advice is enough to solve the problem rapidly (i.e., much faster than in the absence of any advice), whereas it is information insensitive if it requires giving a lot of information to the nodes in order to ensure fast computation of the solution. In this paper, we study the information sensitivity of distributed graph coloring.

Y. Emek, L. Gasieniec, E. Kantor, A. Pelc, D. Peleg, C. Su,
Broadcasting time in UDG radio networks with unknown topology, *Distributed Computing* 21 (2009), 331-351.

Preliminary version appeared in:

Proc. 26th Ann. ACM Symposium on Principles of Distributed Computing (PODC 2007), August 2007, Portland, Oregon, USA, 195-204.

Abstract:

The paper considers broadcasting in radio networks, modeled as unit disk
graphs (UDG).
Such networks occur in wireless communication between sites (e.g.,
stations or sensors) situated in a terrain.
Network stations are represented by points in the Euclidean plane,
where a station is connected to all stations at distance at most 1
from it.
A message transmitted by a station reaches all its neighbors, but a
station hears a message (receives the message correctly) only
if exactly one of its neighbors transmits at a given time step.
One station of the network, called the source, has a message
which has to be disseminated to all other stations.
Stations are unaware of the network topology.
Two broadcasting models are considered.
In the conditional wake up model, the stations other than the
source are initially idle and cannot transmit until they hear a
message for the first time.
In the spontaneous wake up model, all stations are awake (and
may transmit messages) from the beginning.
It turns out that broadcasting time depends on two parameters of the
UDG network, namely, its diameter *D* and its granularity
*g*, which is the inverse of the minimum distance between any two
stations.
We present a deterministic broadcasting algorithm which works in time
*O(Dg)* under the conditional wake up model and prove that
broadcasting in this model cannot be accomplished by any deterministic
algorithm in time better than *Omega (D \sqrt{g})*.
For the spontaneous wake up model, we design two deterministic
broadcasting algorithms: the first works in time *O(D + g ^{2})*
and the second in time

J. Czyzowicz, L. Gasieniec, A. Pelc, Gathering few fat mobile robots in the plane,
*Theoretical Computer Science* 410 (2009), 481-499.

Preliminary version appeared in:

Proc. 10th International Conference on Principles of Distributed Systems (OPODIS'2006), December 2006, Saint-Emilion, France, LNCS 4305, 350-364.

Abstract:

Autonomous identical robots represented by unit discs move deterministically in the plane.
They do not have any common coordinate system, do not communicate, do not have memory of the past and
are totally asynchronous. Gathering such robots means forming a configuration for which the union of all
discs representing them is connected. We solve the gathering problem for three and four robots.
This is the first algorithmic result on gathering robots represented by two-dimesnsional figures rather than
points in the plain: we call such robots *fat*.

P. Flocchini, A. Pelc, N. Santoro, Fault-tolerant sequential scan, *Theory of Computing Systems* 45 (2009), 1-26.

Abstract:

We consider the fault-tolerant version of the sequential scan problem. A line of identical cells has to
be visited by a scanning head. The head can only distinguish an end of the line from an
internal cell but can distinguish neither one end from the other, nor one internal cell from another.
When the head starts at an internal cell, its first move is in a direction chosen by the adversary.
When the head comes to an internal cell from
a neighbor, it has two possible moves: forward, which means ``go to the other neighbor'', and back
which means ``return to the previous neighbor''. At this point the adversary can place a fault whose effect
is the change of the motion direction (going forward instead of back and vice-versa).
The head is not aware of the occurrence of a fault.
The execution cost of a sequential scan algorithm for a line of length $n$ in the presence of at most *k* faults
is the worst-case number of steps that the head must perform in order to scan the entire line. The worst case is taken
over all adversary's decisions. We consider two scenarios: when the length of the line is known to the algorithm
and when it is unknown. Our goal is to construct sequential scan algorithms with minimum execution cost.
We completely solve this problem for known line size. For any parameters *k* and *n*
we construct a sequential scan algorithm, analyze its complexity and prove a matching lower bound, thus showing that
our algorithm is optimal.
The problem of fault-tolerant sequential scan for unknown line size is solved partially. For any parameter *k*
we construct a sequential scan algorithm which explores a line of length *n* with cost *2kn+o(kn)*, for arbitrary *n*.
For *k=1* our algorithm is shown to be optimal. However, we also show an alternative algorithm that has cost at most
*O(kn)* (with a constant larger than 2) for any *n* and cost *kn+o(kn)* (which is asymptotically optimal)
for infinitely many *n*. Hence the asymptotic performances of the two algorithms, for unbounded *k* and *n*,
are incomparable.

A. Pelc, Why do we believe theorems?, *Philosophia Mathematica* III 17 (2009), 84-94.

Abstract:

The formalist point of view maintains that formal derivations underlying proofs, although usually not carried out in practice, contribute to the confidence in mathematical theorems. Opposing this opinion, the main claim of the present paper is that such a gain of confidence obtained from any link between proofs and formal derivations is, even in principle, impossible in the present state of knowledge. Our argument is based on considerations concerning length of formal derivations.