B.S. Chlebus, L. Gasieniec, A. Gibbons, A. Pelc, W. Rytter,
Deterministic broadcasting in ad hoc radio networks,
Distributed Computing 15 (2002), 27-38.
B.S. Chlebus, L. Gasieniec, A. Gibbons, A. Pelc, W. Rytter,
Deterministic broadcasting in ad hoc radio networks,
Distributed Computing 15 (2002), 27-38.
Preliminary version appeared in: Proc. 11th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'2000), San Francisco, USA, January 2000, 861-870.
Abstract:
We consider the problem of distributed deterministic broadcasting in radio networks of unknown topology and size. The network is synchronous. If a node u can be reached from two nodes which send messages in the same round, none of the messages is received by u. Such messages block each other and node u either hears the noise of interference of messages, enabling it to detect a collision, or does not hear anything at all, depending on the model. We assume that nodes are completely ignorant of the network: they know neither its topology, nor size, nor even their immediate neighborhood. The initial knowledge of every node is limited to its own label. We study the time of deterministic broadcasting under this total ignorance scenario. Previous research has concentrated on distributed randomized broadcasting algorithms working for unknown networks, and on deterministic off-line broadcasting algorithms assuming full knowledge of the radio network. Ours are the first broadcasting algorithms simultaneously distributed and deterministic, that work for arbitrary totally unknown radio networks. The results for the model without collision detection: We develop a linear-time broadcasting algorithm for symmetric graphs, which is optimal. For arbitrary n-node graphs, we prove a lower bound Omega(D log n), where D is the diameter, and develop an algorithm working in time O(n11/6). Next we show that broadcasting with acknowledgement is not possible in this model at all. For the model with collision detection, we develop efficient algorithms for broadcasting and for acknowledged broadcasting in strongly connected graphs.
A. Dessmark, A. Pelc,
Deterministic radio broadcasting at low cost, Networks 39 (2002), 88-97.
Preliminary version appeared in: Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2001), February 2001, Dresden, Germany, LNCS 2010, 158-169.
Abstract:
We consider the problem of distributed deterministic broadcasting in radio networks. The network is synchronous. A node receives a message in a given round iff exactly one of its neighbors transmits. The source message has to reach all nodes. We assume that nodes do not know network topology or even their immediate neighborhood. We are concerned with two efficiency measures of broadcasting algorithms: its execution time (number of rounds), and its cost (number of transmissions). We focus our study on execution time of algorithms which have cost close to minimum.
We consider two scenarios depending on whether nodes know or do not know global parameters of the network: the number n of nodes and the eccentricity D of the source. We show that the minimum cost of broadcasting in an n-node network of unknown topology is n, if at least one of the above parameters is unknown, and it is n-1, if both of them are known. Our main contribution are lower bounds on time of low-cost broadcasting which show sharp differences between these scenarios. We show that if nodes know neither n nor D then any broadcasting algorithm whose cost exceeds the minimum by O(n b ), for any constant b <1, must have execution time Omega (Dn log n) for some network. We also show a minimum-cost algorithm that does not assume knowledge of these parameters, and always works in time O (Dn log n). On the other hand, assuming that nodes know either n or D, we show how to broadcast in time O(Dn). This time cannot be improved by any low-cost algorithm knowing even both n and D. Indeed, we show that any algorithm whose cost exceeds the minimum by at most a n, for any constant a <1, requires time Omega (Dn).
In addition, we show that very fast broadcasting algorithms must have high cost. We prove that every broadcasting algorithm that works in time O(nt(n)), where t(n) is polylogarithmic in n, requires cost Omega (n log n / log log n). Since the fastest known broadcasting algorithm works in time O (n log 2 n), its cost (as well as the cost of any faster broadcasting algorithm, if it exists) must be higher than linear.
A. Pelc,
Searching games with errors - Fifty years of coping with liars,
Theoretical Computer Science 270 (2002),
71-109.
Abstract:
This is a survey on searching with errors considered in the framework of two-person games. The Responder thinks of an object in the search space, and the Questioner has to find it by asking questions to which the Responder provides answers, some of which are erroneous. We give a taxonomy of such games, depending on the type of questions allowed, on the degree of interactivity between the players, and on the imposed limitations on errors. We survey the existing results concerning such games, concentrating on the issue of optimizing the Questioner's querying strategy, and pointing out open problems. We show the relations between searching games with errors and problems concerning communication through a noisy channel and error-correcting codes. Finally, we discuss other search and computation problems with faulty feedback which are related to searching with errors.
K. Diks, E. Kranakis, D. Krizanc, A. Pelc,
The impact of information on broadcasting time in linear radio networks,
Theoretical Computer Science 287 (2002), 449-471.
Preliminary version appeared as:
K. Diks, E. Kranakis, D. Krizanc, A. Pelc, The impact of knowledge on broadcasting time in radio networks, Proc. 7th Annual European Symposium on Algorithms, ESA'99, Prague, Czech Republic, July 1999, LNCS 1643, 41-52.
Abstract:
We consider the problem of distributed deterministic broadcasting in radio networks whose nodes are located on a line. Nodes send messages in synchronous time-slots. Each node v has a given transmission range. All nodes located within this range can receive messages from v. However, a node situated in the range of two or more nodes that send messages simultaneously, cannot receive these messages and hears only noise. Each node knows only its own position and range, as well as the maximum of all ranges. Broadcasting is adaptive: Nodes can decide on the action to take on the basis of previously received messages, silence or noise. We prove lower bounds on broadcasting time in this model and construct broadcasting protocols whose performance nearly matches these bounds for the simplest case when nodes are situated on a line. We also show that if nodes do not even know their own range, every broadcasting protocol must be hopelessly slow. While distributed randomized broadcasting algorithms, and, on the other hand, deterministic off-line broadcasting algorithms assuming full knowledge of the radio network, have been extensively studied in the literature, ours are the first results concerning broadcasting algorithms that are distributed and deterministic at the same time. We show that in this case, information available to nodes influences the efficiency of broadcasting in a significant way.