We will introduce the Threshold-driven Streaming Graph model, which is obtained by performing a randomized distributed algorithm, called RAES, over a dynamic graph evolving with the streaming node-churn process. This model captures two key features of modern peer-to-peer networks: a local threshold mechanism that bounds the degree of each vertex, and a node-churn process that regulates how vertices join and leave the network in each round.

Our main result proves good expansion properties of this model, with high probability. As a consequence, we will establish a logarithmic upper bound on the completion time of the well-known PUSH and PULL rumor-spreading protocols. Our analysis will also provide an upper bound to the message-communication overhead, showing that the overall number of exchanged messages at every round t is optimal in expectation and O(log n) with high probability.