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.