Random Walk Based Interaction Protocols

• Applicant: Professorin Dr. Petra Berenbrink
• Subject Area: Theoretical Computer Science
• Term: from 2019 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 427756233

The last few years have seen an increased interest in distributed algorithms in the so-called CONGESTand LOCAL models of communication. The system is modelled by an undirected, connected graph. The nodes of this graph represent computational entities and the edges represent bidirectional communication links. The nodes have a unique ID, and, initially, each node is only aware of its neighbours in the network. Each node is responsible for calculating a part of the output. The communication is done via sending messages to the neighbours in the graph,where details differ between the two main models. In this project we consider a randomised variant of the model where, in each step, every node can send a message to a random subset of the neighbours, possibly just a single one. We are interested mainly in problems related to the spread of information (or disease) and load balancing, and here more specifically Gossiping, Load Balancing and COBRA Walks. Load balancing and gossiping are two fundamental tasks in distributed computing which are necessary for the efficient use of these systems. Cobra walks are a model for the spread of infections and diseases. At first glance these three problems may appear to be unrelated. What does make them related however is the underlying randomised "communication structure" where nodes are allowed to communicate and exchange tokens or messages with randomly selected neighbours. The analysis of these processes heavily relies on techniques used for the analysis of multiple parallel random walks. For example, in the randomised push communication model which is often used for broadcasting and gossiping, nodes can send, in every step, a message to a randomly chosen neighbour. From the point ofview of one message, it looks as if the messages is spread via multiple random walks. In the dimension exchange load balancing approach every nodes balances its load with a randomly chosen neighbour. Hence, the load items perform random walks in the graph. Quite often, and successfully, the methods used to analyse this load balancing scheme are borrowed from theanalysis of random walks. In general, random walks provide a fundamental mathematical model for many processes in networks. Random-walk based processes are fundamental to many areas of systems science, including the study of physical, chemical and biological systems, and to applications in control science. Random walk processes are often analysed in terms of metrics such as hitting times, cover times and mixing times. These quantities, of course, depend on theunderlying structure of the graph which may be expressed in terms of conductance or expansion. The main objective of this project is just that: to analyse the the processes introduced above and to to express their performance in natural random walk based metrics.

• DFG Programme: Research Grants