E. Fusco, A. Pelc, Broadcasting in UDG radio networks with missing and inaccurate information,
Distributed Computing 22 (2010), 167-183.
E. Fusco, A. Pelc, Broadcasting in UDG radio networks with missing and inaccurate information,
Distributed Computing 22 (2010), 167-183.
Preliminary version appeared in:
Proc. 22nd International Symposium on Distributed Computing (DISC 2008), Septembre 2008, Arcachon, France, LNCS 5218, 257-273.
Abstract:
We study broadcasting time in radio networks, modeled as unit disk graphs (UDG). Network stations are represented by points in the plane and a station is connected to all stations at distance at most 1 from it. Stations are unaware of the network topology. Each station can send messages from the beginning of the broadcasting process, even before getting the source message. Emek et al. showed that broadcasting time depends on two parameters of the UDG network, namely, its diameter D (in hops) and its granularity g. The latter is the inverse of the density d of the network which is the minimum Euclidean distance between any two stations. They proved that the minimum broadcasting time is Theta( min {D + g^2, D log g}), assuming that each node knows the density of the network and knows exactly its own position in the plane. In many situations these assumptions are unrealistic. Does removing them influence broadcasting time? The aim of this paper is to answer this question, hence we assume that density is unknown and nodes perceive their position with some unknown error margin $\epsilon$. It turns out that this combination of missing and inaccurate information substantially changes the problem: the main new challenge becomes fast broadcasting in sparse networks (with constant density), when optimal time is O(D). Nevertheless, under our very weak scenario, we construct a broadcasting algorithm that maintains optimal time O( min {D + g^2, D log g}) for all networks with at least 2 nodes, of diameter D and granularityg (previously obtained with exact positions and known density), if each node perceives its position with error margin \epsilon=\alpha d, for any (unknown) constant \alpha <1/2. Rather surprisingly, the minimum time of an algorithm working correctly for all networks, and hence stopping if the source is alone, turns out to be \Theta(D + g^2). Thus, the mere stopping requirement for the special case of the lonely source causes an exponential increase in broadcasting time, for networks of any density and any small diameter. Finally, if \epsilon\geq d/2, then broadcasting is impossible.
A. Pelc, Fault-tolerant strategies in the Iterated Prisoner's Dilemma,
Information Processing Letters 110 (2010), 389-395.
Abstract:
The aim of this paper is to determine how well can strategies in the Iterated Prisoner's Dilemma (IPD) behave in the presence of errors. A highly desirable property of strategies in IPD, even without errors, is their robustness. A strategy \sigma is called 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. For example, the well known simple strategy tit-for-tat is robust. However, tit-for-tat is very vulnerable to errors: already one mistake in its execution can cause it to lose the property of robustness. The ultimate resistance to errors is captured by the notion of perfect fault-tolerance: a strategy has this property, if any distortion of it on an arbitrary finite number of moves remains robust. Do there exist perfectly fault-tolerant strategies in IPD? Somewhat surprisingly, the answer is yes: indeed we describe such a strategy and we prove that it has this very strong resistance to errors. However, we prove that no strategy with bounded memory can have this property. We then go on to show that preserving robustness under distortions on any fixed initial segment of moves is possible with bounded memory.
P. Flocchini, D. Ilcinkas, A. Pelc, N. Santoro,
Remembering without memory: tree exploration by asynchronous oblivious robots,
Theoretical Computer Science 411 (2010), 1544-1557.
Preliminary version appeared in:
Proc. 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2008) June 2008, Villars-sur-Ollon, Switzerland, LNCS 5058, 33-47.
Abstract:
In the effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is Asynch where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles. We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of exploration: within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task. We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that, in general, exploration cannot be done efficiently. More precisely we prove that there are n-node trees where \Omega(n) robots are necessary; this holds even if the maximum degree is 4. On the other hand, we show that if the maximum degree is 3, it is possible to explore with only O(log n/ loglog n) robots. The proof of the result is constructive. We also prove that the size of the team used in our solution is asymptotically optimal: there are trees of degree 3, whose exploration requires \Omega(log n/ loglog n) robots. Our final result shows that the difficulty in tree exploration comes in fact from the symmetries of the tree. Indeed, we show that, in order to explore trees that do not have any non-trivial automorphisms, 4 robots are always sufficient and often necessary.
D. Ilcinkas, D. Kowalski, A. Pelc, Fast radio broadcasting with advice,
Theoretical Computer Science 411 (2010), 1583-1598.
Preliminary version appeared in:
Proc. 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2008) June 2008, Villars-sur-Ollon, Switzerland, LNCS 5058, 291-305.
Abstract:
We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with advice. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under complete knowledge of the network we give a tight answer to the above question: O(n) bits of advice are sufficient but o(n) bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of advice.
P. Fraigniaud, D. Ilcinkas, A. Pelc, Comunication algorithms with advice,
Journal of Computer and System Sciences 76 (2010), 222-232.
Preliminary version appeared as:
Oracle size: a new measure of difficulty for communication problems, Proc. 25th Ann. ACM Symposium on Principles of Distributed Computing (PODC 2006), July 2006, Denver, Colorado, USA, 179-187.
Abstract:
We study the problem of the amount of knowledge about a communication network that must be given to its nodes in order to efficiently disseminate information. While previous results about communication in networks used particular partial information available to nodes, such as the knowledge of the neighborhood or the knowledge of the network topology within some radius, our approach is quantitative: we investigate the minimum total number of bits of information (minimum size of advice) that has to be available to nodes in order to perform efficient communication. It turns out that the minimum size of advice for which a distributed task can be accomplished efficiently can serve as a measure of the difficulty of this task. We use this measure to make a quantitative distinction between the difficulty of two apparently similar fundamental communication primitives: the broadcast and the wakeup. In both of them a distinguished node, called the source, has a message, which has to be transmitted to all other nodes of the network. In the wakeup, only nodes that already got the source message (i.e., are awake) can send messages to their neighbors, thus waking them up. In the broadcast, all nodes can send control messages even before getting the source message, thus potentially facilitating its future dissemination. In both cases we are interested in accomplishing the communication task with optimal message complexity, i.e., using a number of messages linear in the number of nodes. We show that the minimum size of advice permitting the wakeup with a linear number of messages in a n-node network, is Theta (n log n), while the broadcast with a linear number of messages can be achieved with advice of size O(n). We also show that the latter size of advice is almost optimal: no advice of size o(n) can permit to broadcast with a linear number of messages. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.
E. Kranakis, M. Paquette, A.Pelc,
The diameter and connectivity of networks with random dependent faults,
Networks 56 (2010), 103-115.
Preliminary version appeared as:
Communication in networks with random dependent faults, Proc. 32nd International Symposium on Mathematical Foundations of Computer Science, (MFCS 2007), August 2007, Cesky Krumlov, Czech Republic, LNCS 4708, 418-429.
Abstract:
We study the connectivity and diameter of the fault-free part of n-node networks where nodes fail in a random dependent way. To capture fault dependencies, we intro- duce the neighborhood fault model, where damaging events, called spots, occur randomly and independently with probability p at nodes of a network, causing faults in the given node and its neighbors; faults at distance at most 2 become dependent. We investigate the impact of the spot probability on the connectivity and diam- eter of the fault-free part of the network. We show a network which has a low diameter with high probabil- ity, if p \leq 1/c log n We also show that, for constant spot probabilities, most classes of networks do not have their fault-free part connected with high probability.
E. Kranakis, M. Paquette, A. Pelc,
Communication in random geometric radio networks with positively correlated random faults,
Ad Hoc & Sensor Wireless Networks 9 (2010), 23-52.
Preliminary version appeared in:
Proc. 7th International Conference on AD-HOC Networks & Wireless (ADHOC-NOW 2008), September 2008, Sophia Antipolis, France, LNCS 5198, 108-121.
Abstract:
We study the feasibility and time of communication in random geomet- ric radio networks, where nodes fail randomly with positive correlation. We consider a set of radio stations with the same communication range, distributed in a random uniform way on a unit square region. In order to capture fault dependencies, we introduce the ranged spot model in which damaging events, called spots, occur randomly and independently on the region, causing faults in all nodes located within distance s from them. Node faults within distance 2s become dependent in this model and are positively correlated. We investigate the impact of the spot arrival rate on the feasibility and the time of communication in the fault-free part of the network. We provide an algorithm which broadcasts correctly with probability 1 - e in faulty random geometric radio networks of diameter D in time O(D + log 1/e).