Abstracts of papers published in 2009


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 + g2) and the second in time O(D log g). While neither of these algorithms alone is optimal for all parameter values, we prove that the algorithm obtained by interleaving their steps, and thus working in time O (min{D + g2, D log g}, turns out to be optimal by establishing a matching lower bound.

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.