Stochastic analyses of dynamic computer processes
Eli Upfal, Gopalakrishnan C. Pandurangan · 2002
Stochastic processes can model a variety of dynamic computer phenomena such as traffic in communication networks, input for packet routing or caching or load balancing, growth of the World Wide Web, and evolving structure of dynamic networks. Stochastic analysis enables us to characterize properties of such processes that dynamically change with time. In this thesis, we present four results in different settings in which stochastic processes serve as natural models for dynamic computer phenomena that arise in practical applications. The models are useful not only in understanding these phenomena but also in designing and analyzing practical algorithms for associated problems. The results are: (1) Communication Networks: We address the problem of evaluating Quality-of-Service (QoS) properties in statistically multiplexed communication networks fed by bursty sources. Using a stochastic model for bursty sources, we give efficient Monte-Carlo algorithms for estimating the failure probability of an arbitrary topology network under static and dynamic settings. (2) Peer-to-Peer Networks: We address the fundamental problem of building Peer-to-Peer (P2P) networks with good topological properties. We present a simple and practical distributed local protocol for building P2P networks and prove under a reasonable stochastic model that it results in connected networks of constant degree and logarithmic diameter. (3) Online Computation: We propose a novel way of measuring online performance based on the characteristics of the input sequence; this is fundamentally different from the standard competitive analysis of online computation. Assuming a very general stochastic model for the input sequence, we present bounds between entropy of the input and the performance of the best online algorithm for classical online problems such as prefetching, caching, and load balancing. (4) Web Models: We develop and analyze new stochastic models for the Web graph which capture a global property of the Web: the PageRank distribution. Our models explain the PageRank distribution while remaining faithful to the previously studied degree distributions.