In this talk, I will present two results in different settings in which stochastic processes serve as natural models for dynamic computer phenomena. The models are useful not only in understanding these phenomena but also in designing practical algorithms/schemes for the associated algorithmic problems. The two results are:
(1) Stochastic Analysis of Peer-to-Peer (P2P) Networks : I will first motivate the problem of building connected low-diameter P2P networks. Then I will present a simple distributed protocol for building P2P networks and prove (under a reasonable stochastic model) that it results in connected networks of constant degree and logarithmic diameter. An important feature of our protocol is that it operates without any global knowledge of all the nodes in the network. To our knowledge, this is the first such protocol with provable guarantees on connectivity and diameter.
(2) Stochastic Analysis of Online Computation: In the second part of the talk, I will discuss a novel way of measuring online performance based on the characteristics of the input sequence; this is fundamentally different from the traditional competitive analysis of online computation. Assuming a very general stochastic model for the input sequence, I will present bounds between entropy of the input and the performance of the best online algorithm for various online problems. In particular, I will present a simple online algorithm for prefetching and show that it performs well on any input sequence. I will also mention a few practical applications of our approach.