GR/M37561

Principal investigator: Prof. Alan Michael Gibbons

Co-investigators: Prof. Wojciech Rytter and Dr. Leszek Gasieniec

EPSRC Visiting Fellowship for Prof. Andrzej Pelc, Quebec University, Hull, Canada

The general aim of the 6th months project was to study of communication
methods, designed for networks whose topology is partially or totally
unknown and subject to component failure.
This includes construction of efficient communication algorithms for
networks lacking some crucial topological knowledge, as well as construction
of efficient algorithms for the tasks of * broadcasting* and information
exchange in networks whose links and/or nodes are subject to failures.
The emphasis was on design provably optimal or asymptotically optimal
algorithms trying to establish corresponding lower bounds as evidence of
their efficiency.

The joint research with prof. Andrzej Pelc was mainly
focused on communication in radio networks of unknown topology and size.
A * radio network* is a
collection of transmitter-receiver devices, referred to as * nodes*.
Every node can reach a given subset of other nodes, depending on the power of
its transmitter and on topographic characteristics of the surrounding region.
Nodes send messages in synchronous *rounds* or *time slots*,
measured by a global clock which indicates the current round number.
In every round every node acts either as a *transmitter* or as
a *receiver*.
A node acting as a receiver in a given round gets a message iff exactly
one of its neighbors transmits in this round. The message received
is the one that was transmitted. If at least two neighbors of $u$ transmit
in a given round, none of the messages is received by $u$ in this round.
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 assumed that nodes are completely ignorant of the network: they
know neither its topology, nor size, nor even their immediate neighborhood.
And the initial knowledge of every node is limited to its own label.
We studied the time of deterministic *broadcasting* under this total
ignorance scenario, see [1].
Our algorithm is the first broadcasting algorithms simultaneously
distributed and deterministic, that work for arbitrary totally unknown
radio networks.

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(n^{11/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.

Finally we performed investigation of communication abilities of radio networks with unsynchronized local clocks, see [3].

During his visit in United Kingdom prof. Pelc gave seminars at Liverpool University and King's College London. He contributed also to Liverpool Algorithms Day (LAD'99) organised by our Algorithms Group in June 1999. Moreover we made a major revision of our earlier paper devoted to deterministic computation on PRAM with static faults, see [2].

** Acknowledgement** We would like to thank EPSRC for funding the project.

[1] B.S.Chlebus, L.Gasieniec, A.Gibbons, A.Pelc, and W.Rytter, Deterministic broadcasting in unknown radio networks ©, In Proceedings of 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2000), San Francisco, January 2000.

[2] B.S.Chlebus, L.Gasieniec, and A.Pelc,
Deterministic Computations on a PRAM with Static Faults,
submitted to *Information and Computation*.

[3] L.Gasieniec, A.Pelc, and D.Peleg, The Wakeup Problem in Synchronous Broadcast Systems ©, In Proceedings of 19th ACM Symposium on Principles of Distributed Computing (PODC'00), Portland, July 2000.