##### Department of Mathematics,

University of California San Diego

****************************

### Combinatorics Reading

## Robert Elsaesser

#### UCSD

## Bounding the Communication Complexity of Randomized Broadcasting in Random-Like Graphs

##### Abstract:

Broadcasting algorithms have a various range of application in differentfields of computer science. In this paper we study the communicationcomplexity of simple randomized broadcasting algorithms in random-like networks. We start our analysis on the classical random graph model, i.e., a graph $G_p$ with $n$ nodes is constructed by letting any two arbitrary nodes be connected with probability $p$. First, we state some combinatorial results which are necessary for our main study. \vskip .1in \noindent Then, we consider a modified version of the random phone call model intorduced by Karp et al., and show that the communication complexity of the corresponding broadcasting algorithm is bounded by an asymptotically optimal value in almost all connected random graphs. More precisely, we show that if $p$ exceeds some threshold, then we are able to broadcast any information $r$ in a random graph $G_p$ of size $n$ within $O(\log n)$ steps by using at most $O(n \max\{ \log \log n, \log n/\log d\})$ transmissions of $r$, where $d=pn$ denotes the expected average degree in $G_p$. This result holds with probability $1- o(1/n^c)$, where $c$ is a constant, even if $n$ and $d$ are unknown to the nodes of the graph. \vskip .1in \noindent The main result of the paper can be extended to other random graph models as well. A slight modification of our algorithm results in asymptotically optimal communication overhead for certain types of the random power law graphs defined by Chung and Lu. It is worth mentioning that such random power law graphs are often used to model large scale real world networks such as the Internet. \vskip .1in \noindent The algorithm we present in this paper is simple, scalable, and robust. It can efficiently handle restricted communication failures and certain changes in the size of the network. In addition, our methods and the auxiliary combinatorial results might be useful for further investigation on this field.

Host:

### July 28, 2005

### 1:00 PM

### AP&M 7321

****************************