Efficient communication in unknown networks

We consider the problem of disseminating messages in networks. We are inter ested in information dissemination algorithms in which machines operate ind ependently without any knowledge of the network topology or sire. Three com munication tasks of increasing difficulty are studied. In blind broadcastin g (BB), the goal is to communicate the source message to all nodes. In ackn owledged blind broadcasting (ABB), the goal is to achieve BE and inform the source about it. Finally, in fall synchronization (FS), all nodes must sim ultaneously enter the state terminated after receiving the source message. The algorithms should be efficient both in terms of the time required and t he communication overhead they put on the network. We limit the latter by a llowing every node to send a message to at most one neighbor in each round. We show that BE is achieved in time at most 2n in any n-node network and s how networks in which time 2n - o(n) is needed. For ABB, we show algorithms working in time (2 + epsilon )n, for any fixed positive constant epsilon a nd sufficiently large n, Thus, for both BE and ABS, our algorithms are clos e 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 tim e of full synchronization remains an open problem. (C) 2001 John Wiley & So ns, Inc.