L. Gargano, A. Pelc, S. Perennes, U. Vaccaro,
Efficient communication in unknown networks,
Networks 38 (2001),39-49.
L. Gargano, A. Pelc, S. Perennes, U. Vaccaro,
Efficient communication in unknown networks,
Networks 38 (2001),39-49.
Preliminary version appeared in:
Proc. 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'2000), June 2000, Konstanz, Germany, LNCS 1928, 172--183.
Abstract:
We consider the problem of disseminating messages in networks. We are interested in information dissemination algorithms in which machines operate independently without any knowledge of the network topology or size. Three communication tasks of increasing difficulty are studied. In blind broadcasting (BB) the goal is to communicate the source message to all nodes. In acknowledged blind broadcasting (ABB) the goal is to achieve BB and inform the source about it. Finally, in full synchronization (FS) all nodes must simultaneously enter the state {\em terminated} after receiving the source message. The algorithms should be efficient both in terms of the time required and the communication overhead they put on the network. We limit the latter by allowing every node to send a message to at most one neighbor in each round. We show that BB is achieved in time at most 2n in any n-node network and show networks in which time 2n-o(n) is needed. For ABB we show algorithms working in time (2+e)n, for any fixed positive constant e and sufficiently large n. Thus for both BB and ABB our algorithms are close to optimal. Finally, we show a simple algorithm for FS working in time 3n, and a more complicated algorithm which works in time 2.9n. The optimal time of full synchronization remains an open problem.
P. Fraigniaud, A. Pelc, D. Peleg, S. Perennes,
Assigning labels in an unknown anonymous network with a leader,
Distributed Computing 14 (2001), 163-183.
Preliminary version appeared as:
P. Fraigniaud, A. Pelc, D. Peleg, S. Perennes, Assigning labels in unknown anonymous networks, Proc. 19th Ann. ACM Symposium on Principles of Distributed Computing (PODC'2000), Portland, Oregon, U.S.A., July 2000, 101-112.
Abstract:
We consider the task of assigning distinct labels to nodes of an unknown anonymous network in a distributed manner. A priori, nodes do not have any identities, except for one distinguished node, called the source, and do not know the topology or the size of the network. They execute identical algorithms, apart from the source which plays the role of a leader and starts the labeling process. Our goal is to assign short labels, as fast as possible. The quality of a labeling algorithm is measured by the range from which the algorithm picks the labels, or alternatively, the length of the assigned labels. Natural efficiency measures are the time, i.e., the number of rounds required for the label assignment, and the message and bit complexities of the label assignment protocol, i.e., the total number of messages (resp., bits) circulating in the network. We present label assignment algorithms whose time and message complexity are asymptotically optimal and which assign short labels. On the other hand, we establish inherent trade-offs between quality and efficiency for labeling algorithms.
L. Gasieniec, A. Pelc, D. Peleg,
The wakeup problem in synchronous broadcast systems,
SIAM Journal on Discrete Mathematics 14 (2001), 207-222.
Preliminary version appeared in:
Proc. 19th Ann. ACM Symposium on Principles of Distributed Computing (PODC'2000), Portland, Oregon, U.S.A., July 2000, 113-122.
Abstract:
This paper studies the differences between two levels of synchronization in a distributed broadcast system (or a multiple access channel). In the globally synchronous model, all processors have access to a global clock. In the locally synchronous model, processors have local clocks ticking at the same rate, but each clock starts individually, when the processor wakes up. We consider the fundamental problem of waking up all of n processors of a completely connected broadcast system. Some processors wake up spontaneously, while others have to be woken up. Only awake processors can send messages; a sleeping processor is woken up upon hearing a message. The processors hear a message in a given round if and only if exactly one processor sends a message in that round. Our goal is to wake up all processors as fast as possible in the worst case, assuming an adversary controls which processors wake up and when. We analyze the problem in both the globally synchronous and locally synchronous models, with or without the assumption that n is known to the processors. We propose randomized and deterministic algorithms for the problem, as well as lower bounds in some of the cases. These bounds establish a gap between the globally synchronous and locally synchronous models.
E. Kranakis, D. Krizanc, A. Pelc,
Fault-tolerant broadcasting in radio networks,
Journal of Algorithms 39 (2001), 47-67.
Preliminary version appeared in:
Proc. 6th Annual European Symposium on Algorithms, ESA'98, Venice, Italy, August 1998, LNCS 1461, 283-294.
Abstract:
We consider broadcasting in radio networks that are subject to permanent node failures of unknown location. Nodes are spread in a region in some regular way. We consider two cases: nodes are either situated at integer points of a line or they are situated on the plane, at grid points of a square or hexagonal mesh. Nodes send messages in synchronous time-slots. Each node v has a given transmission range of the same radius R. 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. Faulty nodes do not receive or send any messages. We give broadcasting algorithms whose worst-case running time has optimal order of magnitude, and we prove corresponding lower bounds. In case of nonadaptive algorithms this order of magnitude is Theta(D+t), and for adaptive algorithms it is Theta(D+log (min(R,t))), where t is an upper bound on the number of faults in the network and D is the diameter of the fault-free part of the network that can be reached from the source as a result of those faults.
G. De Marco, A. Pelc,
Faster broadcasting in unknown radio networks,
Information Processing Letters 79 (2001), 53-56.
Abstract:
We study the time of distributed deterministic broadcasting in synchronous radio networks of unknown topology and size. 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. 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 show how to broadcast in time O(n5/3(log n)1/3).