Information Dissemination in Large Networks
Framework
Information dissemination in large networks has various fields of application in distributed computing. Consider for example the maintenance of replicated databases in name servers in a large corporate networks. There are updates injected at various nodes, and these updates must be propagated to all the nodes in the network. In order to let all copies of the database converge to the same content, efficient broadcasting algorithms have to be developed.There is an enormous amount of experimental and theoretical study of (deterministic and randomized) broadcasting in various models and on different networks. We are mainly interested in the runtime and communication overhead produced by randomized broadcasting algorithms. As an example, consider the so-called push algorithm: In a graph we place at some time t a piece of information on one of the nodes. Then, in each succeeding time step, any informed vertex forwards a copy of this information to a neighbor selected independently and uniformly at random.
The advantage of randomized broadcasting is its inherent robustness against failures and dynamical changes compared to deterministic schemes that either need substantially more time or can tolerate only a relatively small number of faults. In our research group we analyze and develop simple randomized broadcasting algorithms with the following properties:
- They can successfully handle restricted communication failures in the network.
- They work well if size or topology of the network change slightly while the algorithm is executed.
- The number of message transmissions they produce is asymptotically minimal.
We analyzed the simple broadcasting algorithm described above on arbitrary graphs, as well as on some specific network topologies. We established new lower bounds which provide evidence that complete graphs are the best graphs for time efficient broadcasting. We also gave tight upper bounds on the runtime for several graph classes. Furthermore, we considered the behaviour of the push algorithm if transmissions are not always sent succesfully. Also in this noisy environment, the push algorithm is still time-efficient, provided that the transmissions are succesful with a constant probability.
We also considered the relationship between random walks and the runtime of the push algorithm. We showed that the runtime of this algorithm is upper bounded by the mixing time of a corresponding random walk and an additional logarithmic factor. Moreover, we analyzed the behaviour of the push algorithm on Cayley graphs by using martingale-based techniques.
Another main objective is to reduce the message complexity produced by simple randomized broadcasting without increasing the runtime. To achieve this goal, the so called pull model has been introduced. In this model, each (informed or uninfored) node chooses in every step a neighbor, uniformly at random, and uninformed nodes are allowed to pull information from informed nodes called by this node in a specific step. This kind of transmission makes sense if at almost every node updates occur frequently so that almost every node places a random call in each round anyway. It was shown that by combining push and pull it is possible to significantly reduce the number of message transmissions in a complete graph. Recently, we analyzed this combined model on certain random graph classes and determined the behavior of randomized broadcasting in certain random networks.
Projects
Contact
Robert Elsässer (elsa@upb.de)Thomas Sauerwald (sauerwal@upb.de)