On trees, graphs, clouds and heavy tails
Mariana Olvera-Cravioto, Columbia University, USA

Abstract: During this talk we will discuss two problems whose solution entails the analysis of stochastic fixed point equations on weighted branching trees. The first one is related to the analysis of PageRank type ranking algorithms on random graphs. In particular, we study the probability distribution of the rank of a randomly chosen node in a configuration graph, which leads through a node exploration process to a coupling with a weighted branching tree and the solution to a linear recursion. The second problem arises from the analysis of queueing networks with parallel processors and synchronization requirements, such as those encountered in today's cloud computing algorithms, e.g. MapReduce. In this case, we analyze the waiting time of a job that upon arrival to the system is split up into several pieces of similar size and then randomly routed to different servers, with the constraint that all pieces of the job must begin their service at the same time. The analysis of the so-called predecessor graph of a job leads to a maximum type recursion on a weighted branching tree. We then tie the two problems together by discussing the stochastic fixed point equations on weighted branching trees that appear in the limit, and how their solutions exhibit in great generality a heavy-tailed behavior. 

Aalto Stochastics & Statistics Seminar
Mon 25 Aug 2014, 16:15-17:15
Lecture Hall M2, Otakaari 1, Espoo