Projects per year
Abstract
Information propagation on graphs is a fundamental topic in distributed computing. One of the simplest models of information propagation is the push protocol in which at each round each agent independently pushes the current knowledge to a random neighbour. In this paper we study the socalled coalescingbranching random walk (COBRA), in which each vertex pushes the information to κ randomly selected neighbours and then stops passing information until it receives the information again. The aim of COBRA is to propagate information fast but with a limited number of transmissions per vertex per step. In this paper we study the cover time of the COBRA process defined as the minimum time until each vertex has received the information at least once. Our main result says that if G is an nvertex r regular graph whose transition matrix has second eigenvalue λ, then the COBRA cover time of G is O(log n), if 1  λ is greater than a positive constant, and O((log n)=(1  λ)^{3})), if 1  λ ≫ √ log(n)/n. These bounds are independent of r and hold for 3 ≤ r ≤ n  1. They improve the previous bound of O(log^{2} n) for expander graphs [Dutta et al., SPAA 2013]. Our main tool in analysing the COBRA process is a novel duality relation between this process and a discrete epidemic process, which we call a biased infection with persistent source (BIPS). A fixed vertex v is the source of an infection and remains permanently infected. At each step each vertex u other than v selects k neighbours, independently and uniformly, and u is infected in this step if and only if at least one of the selected neighbours has been infected in the previous step. We show the duality between COBRA and BIPS which says that the time to infect the whole graph in the BIPS process is of the same order as the cover time of the COBRA process.
Original language  English 

Title of host publication  Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing 
Publisher  ACM New York, NY, USA 
Pages  461467 
Number of pages  7 
Volume  2529July2016 
ISBN (Electronic)  9781450339643 
DOIs  
Publication status  Published  2016 
Event  35th ACM Symposium on Principles of Distributed Computing, PODC 2016  Chicago, United States Duration: 25 Jul 2016 → 28 Jul 2016 
Conference
Conference  35th ACM Symposium on Principles of Distributed Computing, PODC 2016 

Country/Territory  United States 
City  Chicago 
Period  25/07/2016 → 28/07/2016 
Keywords
 Cover time
 Epidemic processes
 Random processes on graphs
Fingerprint
Dive into the research topics of 'The coalescingbranching random walk on expanders and the dual epidemic process'. Together they form a unique fingerprint.Projects
 1 Finished

Randomized Algorithms for Computer Networks
EPSRC Engineering and Physical Sciences Research Council
1/09/2014 → 31/10/2017
Project: Research