## Abstract

We study gossip algorithms for the rumor spreading problem which asks one node to deliver a rumor to all nodes in an unknown network, and every node is only allowed to call one neighbor in each round. In this work we introduce two fundamentally new techniques in studying the rumor spreading problem:

First, we establish a new connection between the rumor spreading process in an arbitrary graph and certain Markov chains. While most previous work analyzed the rumor spreading time in general graphs by studying the rate of the number of (un-)informed nodes after every round, we show that the mixing time of a certain Markov chain suffices to bound the rumor spreading time in an arbitrary graph.

Second, we construct a reduction from rumor spreading processes to branching programs. This reduction gives us a general framework to derandomize the rumor spreading and other gossip processes. In particular, we show that, for

First, we establish a new connection between the rumor spreading process in an arbitrary graph and certain Markov chains. While most previous work analyzed the rumor spreading time in general graphs by studying the rate of the number of (un-)informed nodes after every round, we show that the mixing time of a certain Markov chain suffices to bound the rumor spreading time in an arbitrary graph.

Second, we construct a reduction from rumor spreading processes to branching programs. This reduction gives us a general framework to derandomize the rumor spreading and other gossip processes. In particular, we show that, for

*any n*-vertex expander graph, there is a protocol which informs every node in*O*(log*n*) rounds with high probability, and uses*O*(log*n*· log log*n*) random bits in total. The runtime of our protocol is tight, and the randomness requirement of*O*(log*n*· log log*n*) random bits almost matches the lower bound of Ω(log*n*) random bits. We further show that, for many graph families (defined with respect to the expansion and the degree),*O*(poly log*n*) random bits in total suffice for fast rumor spreading. These results give us an almost complete understanding of the role of randomness in the rumor spreading process, which was extensively studied over the past years.Original language | English |
---|---|

Title of host publication | Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015 |

Publisher | SIAM |

Pages | 411-430 |

Number of pages | 20 |

ISBN (Electronic) | 978-1-61197-373-0 |

ISBN (Print) | 978-1-61197-374-7 |

DOIs | |

Publication status | Published - 2015 |

Event | ACM-SIAM Symposium on Discrete Algorithms - Westin San Diego Gaslamp Quarter, San Diego, United States Duration: 4 Jan 2015 → 6 Jan 2015 http://www.siam.org/meetings/da15/ |

### Conference

Conference | ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Abbreviated title | SODA |

Country/Territory | United States |

City | San Diego |

Period | 4/01/15 → 6/01/15 |

Internet address |