D. Kowalski, A. Pelc,
Time of deterministic broadcasting in radio networks with local knowledge,
SIAM Journal on Computing 33 (2004), 870-891.
D. Kowalski, A. Pelc,
Time of deterministic broadcasting in radio networks with local knowledge,
SIAM Journal on Computing 33 (2004), 870-891.
Preliminary version appeared as:
Deterministic broadcasting time in radio networks of unknown topology, Proc. 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002), November 2002, Vancouver, Canada, 63-72.
Abstract:
In a seminal paper [BGI]
R. Bar-Yehuda, O. Goldreich, and A. Itai, On the time complexity of broadcast in radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences 45 (1992), 104-126.
the authors considered broadcasting in radio networks whose nodes know only their own label and labels of their neighbors. They proved a linear lower bound on the time of deterministic broadcasting in such radio networks, by constructing a class of graphs of diameter 3, with the property that every broadcasting algorithm requires linear time on one of these graphs. Due to a subtle error in the argument, this result is incorrect. We construct an algorithm that broadcasts in logarithmic time on all graphs from [BGI]. Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter o(log log n). On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time Omega(sqrt[4]{n}) on one of these graphs. In view of the randomized algorithm from [BGI], runnning in expected time O(D log n + log 2 n) on all n-node graphs of diameter D, our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting.
A. Dessmark, A. Pelc,
Optimal graph exploration without good maps,
Theoretical Computer Science 326 (2004), 343-362.
Preliminary version appeared in:
Proc. 10th European Symposium on Algorithms (ESA 2002), September 2002, Rome, Italy, LNCS 2461, 374-386.
Abstract:
A robot has to visit all nodes and traverse all edges of an unknown undirected connected graph, using as few edge traversals as possible. The quality of an exploration algorithm is measured by comparing its cost (number of edge traversals) to that of the optimal algorithm having full knowledge of the graph. The ratio between these costs, maximized over all starting nodes in the graph and over all graphs in a given class, is called the overhead of algorithm for this class of graphs. We consider three scenarios, providing the robot with varying amount of information. The robot may either know nothing about the explored graph, or have an unlabeled isomorphic copy of it (an unanchored map), or have such a copy with a marked starting node (an anchored map). For all of the above scenarios, we construct natural exploration algorithms that have smallest, or - in one case - close to smallest, overhead. An important contribution of this project is establishing lower bounds that prove optimality of these exploration algorithms.
D. Kowalski, A. Pelc,
Faster deterministic broadcasting in ad hoc radio networks,
SIAM Journal on Discrete Mathematics 18 (2004), 332-346.
Preliminary version appeared in:
Proc. 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003), February/March 2003, Berlin, Germany, LNCS 2607, 109-120.
Abstract:
We consider radio networks modeled as directed graphs. In ad hoc radio networks, every node knows only its own label and a linear bound on the size of the network but is unaware of the topology of the network, or even of its own neighborhood. The fastest currently known deterministic broadcasting algorithm working for arbitrary n-node ad hoc radio networks, has running time O (n log 2 n). Our main result is a broadcasting algorithm working in time O (n log n log D) for arbitrary n-node ad hoc radio networks of radius D. The best currently known lower bound on broadcasting time in ad hoc radio networks is Omega (n log D), hence our algorithm is the first to shrink the gap between bounds on broadcasting time in radio networks of arbitrary radius to a logarithmic factor. We also show a broadcasting algorithm working in time O (n log D) for complete layered n-node ad hoc radio networks of radius D. The latter complexity is optimal.
K. Diks, P. Fraigniaud, E. Kranakis, A. Pelc,
Tree exploration with little memory, Journal of Algorithms 51 (2004), 38-63.
Preliminary version appeared in:
Proc. 13th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'2002), San Francisco, U.S.A., January 2002, 588-597.
Abstract:
A robot with k-bit memory has to explore a tree whose nodes are unlabeled and edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the tree or of its size, and its aim is to traverse all the edges. While O(log Delta) bits of memory suffice to explore any tree of maximum degree Delta if stopping is not required, we show that bounded memory is not sufficient to explore with stop all trees of bounded degree (indeed Omega(log log log n) bits of memory are needed for some such trees of size n). For the more demanding task requiring to stop at the starting node after completing exploration, we show a sharper lower bound Omega (log n) on required memory size, and present an algorithm to accomplish this task with O(log 2 n)-bit memory, for all n-node trees.
S. Dobrev, A. Pelc, Leader election in rings with nonunique labels,
Fundamenta Informaticae 59 (2004), 333-347.
Preliminary version appeared in:
Proc. 2003 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'03), June 2003, Las Vegas, U.S.A., 1400-1406.
Abstract:
We consider the leader election problem in a ring whose nodes have possibly nonunique labels. Every node knows a priori its own label and two integers, m and M, which are, respectively, a lower and an upper bound on the (unknown) size n of the ring. The aim is to decide whether leader election is possible and to perform it, if so. We consider both the synchronous and the asynchronous version of the problem and we are interested in message complexity in both cases. For the synchronous version we present an algorithm using O(n log n) messages and working in time O(M). Moreover, our algorithm uses O(n) messages when all identifiers are distinct. For the asynchronous version we show an Omega(nM) lower bound on message complexity for this problem, and present an algorithm for it using O(nM) messages.
A. Dessmark, A. Pelc, Distributed coloring and communication in rings with local knowledge,
Combinatorics, Probability and Computing 13 (2004), 123-136.
Preliminary version appeared in:
Proc. International Parallel and Distributed Processing Symposium (IPDPS 2001), San Francisco, U.S.A., April 2001.
Abstract:
We consider two interrelated tasks in a synchronous n-node ring: distributed constant coloring and local communication. We investigate the impact of the amount of knowledge available to nodes on the time of completing these tasks. Every node knows the labels of nodes up to a distance r from it, called the knowledge radius. In distributed constant coloring every node has to assign itself one out of a constant number of colors, so that adjacent nodes get different colors. In local communication every node has to communicate a message to both of its neighbors. We study these problems in two popular communication models: the one-way model in which each node can only either transmit to one neighbor or receive from one neighbor, in any round, and the radio model in which simultaneous receiving from two neighbors results in interference noise. Hence the main problem in fast execution of the above tasks is breaking symmetry with restricted knowledge of the ring. We show that distributed constant coloring and local communication are tightly related and one can be used to accomplish the other. Also in most situations the optimal time is the same for both of them, and it strongly depends on knowledge radius.