D. Kowalski, A. Pelc,
Broadcasting in undirected ad hoc radio networks,
Distributed Computing 18 (2005), 43-57.
D. Kowalski, A. Pelc,
Broadcasting in undirected ad hoc radio networks,
Distributed Computing 18 (2005), 43-57.
Preliminary version appeared in:
Proc. 22nd Ann. ACM Symposium on Principles of Distributed Computing (PODC'2003), July 2003, Boston, U.S.A., 73-82.
Abstract:
We consider distributed broadcasting in radio networks, modeled as undirected graphs, whose nodes have no information on the topology of the network, nor even on their immediate neighborhood. For randomized broadcasting, we give an algorithm working in expected time O (D log(n/D) + log 2 n) in n-node radio networks of diameter D, which is optimal, as it matches the lower bounds of Alon et al. and Kushilevitz and Mansour. Our algorithm improves the best previously known randomized broadcasting algorithm of Bar-Yehuda, Goldreich and Itai, running in expected time O (D log n + log 2 n). (In fact, our result holds also in the setting of n-node directed radio networks of radius D.) For deterministic broadcasting, we show the lower bound Omega ((n log n) / log (n/D)) on broadcasting time in n-node radio networks of diameter D. This implies previously known lower bounds of Bar-Yehuda, Goldreich and Itai and Bruschi and Del Pinto, and is sharper than any of them in many cases. We also give an algorithm working in time O (n log n), thus shrinking -- for the first time -- the gap between the upper and the lower bound on deterministic broadcasting time to a logarithmic factor.
P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc, D. Peleg,
Graph exploration by a finite automaton,
Theoretical Computer Science 345 (2005), 331-344.
Preliminary version appeared in:
Proc. 29th International Symposium on Mathematical Foundations of Computer Science (MFCS'2004), August 2004, Prague, Czech Republic, LNCS 3153, 451-462.
Abstract:
A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K-state robot and any d>2, there exists a planar graph of maximum degree d with at most K+1 nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs Omega(D log d} memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS up to depth D+1 enables a robot to explore any graph of diameter D and maximum degree d using a memory of size O(D log d) bits. We thus prove that the worst case space complexity of graph exploration is Theta(D log d) bits.
J. Czyzowicz, W. Fraczak, A. Pelc,
Transducers with set outputs,
Journal of Automata, Languages and Combinatorics 10 (2005), 37-49.
Preliminary version appeared in:
Proc. 8th Annual International Computing and Combinatorics Conference (COCOON 2002), Singapore, August 2002, 300-309.
Abstract:
We consider transducers with set output, i.e., finite state machines which produce a set of output symbols upon reading any input symbol. When a word consisting of input symbols is read, the union of corresponding output sets is produced. Such transducers are instrumental in some important data classification tasks, such as multi-field packet classification. Two transducers are called equivalent if they produce equal output upon reading any input word. In practical data classification applications, it is important to store in memory only one transducer of every equivalence class, in order to save memory space. This yields the need of finding, in any equivalence class, one transducer, called canonical which is easy to compute, given any transducer from this class. One of the results of this paper is the construction of an algorithm which completes this task. Assuming that the input and output alphabets are of bounded size, for a given n-state transducer T, our algorithm finds the canonical transducer T' equivalent to T in time O(n log n).
A. Pelc, D. Peleg,
Broadcasting with locally bounded Byzantine faults,
Information Processing Letters 93 (2005), 109-115.
Abstract:
We consider broadcast in the presence of Byzantine node failures, under the t-locally bounded model: at most t faults are allowed in the neighborhood of every node. This problem was considered for specific ``geometric'' graphs by Koo, while we study it in the context of arbitrary graphs. We first establish an upper bound on t for which a simple broadcast algorithm proposed by Koo, the Certified Propagation Algorithm (CPA), works correctly for arbitrary graphs, under the t-locally bounded scenario, and a lower bound on t for which no broadcast algorithm can work. Since CPA does not use any global knowledge of network topology, both these results hold regardless of whether the topology of the network is known or if the network is ad hoc. The situation when t is between these bounds turns out to be quite complex. On the one hand we show a graph for which CPA still works, and on the other hand we show a graph for which CPA does not work but some other broadcast algorithm does. The algorithm in the second example is an extension of CPA by a rule similar to that in Dolev's Purifying Algorithm, and it requires knowledge of the topology of the graph. Knowledge of topology turns out to be essential in our context. The separation between broadcast algorithms knowing the topology of the network and ad hoc algorithms is evidenced by the following result: there exists a graph for which some 1-locally fault-tolerant algorithm exists, if the knowledge of the graph is assumed but no such algorithm exists otherwise.
D. Kowalski, A. Pelc,
Time complexity of radio broadcasting: adaptiveness vs. obliviousness and
randomization vs. determinism,
Theoretical Computer Science 333 (2005), 355-371.
Preliminary version appeared in:
Proc. 10th Colloquium on Structural Information and Communication Complexity (SIROCCO 2003), June 2003, Umea, Sweden, 195-210.
Abstract:
We consider the time of broadcasting in ad hoc radio networks modeled as undirected graphs. In such networks, every node knows only its own label and a linear bound on the number of nodes but is unaware of the topology of the network, or even of its own neighborhood. Our aim is to study to what extent the availability of two important characteristics of a broadcasting algorithm influences optimal broadcasting time. These characteristics are adaptiveness and randomization. Our contribution is establishing upper and lower bounds on optimal broadcasting time for three classes of algorithms: adaptive deterministic, oblivious randomized and oblivious deterministic. In two cases we present tight bounds, and in one case a small gap remains. We show that for deterministic adaptive algorithms time Omega (n) is required even for n-node networks of constant diameter. This lower bound is strongest possible, since linear time algorithms are known, and hence establishes optimal time Theta (n) for this class. For oblivious randomized algorithms we show an upper bound O(n min{D, log n}) and a lower bound Omega (n) on optimal expected broadcasting time in n-node networks of diameter D. Finally, for oblivious deterministic algorithms we show matching upper and lower bounds Theta(n min{D, sqrt{n}}) on optimal broadcasting time. Our results imply that enforcing obliviousness has at least as strong negative impact on broadcasting time as enforcing determinism, and that algorithms having both these features are strictly less efficient than those having only one of them.