title: Invasion percolation on a tree and queueing models.
abstract: We study the properties of the Barabási model of queuing [A.-L. Barabási, Nature (London) 435, 207 (2005); J. G. Oliveira and A.-L. Barabási, Nature (London) 437, 1251 (2005)] in the hypothesis that the number of tasks grows with time steadily. Our analytical approach is based on two ingredients. First we map exactly this model into an invasion percolation dynamics on a Cayley tree. Second we use the theory of biased random walks. In this way we obtain the following results: the stationary-state dynamics is a sequence of causally and geometrically connected bursts of execution activities with scale-invariant size distribution. We recover the correct waiting-time distribution PW(tau) approximately tau(-3/2) at the stationary state (as observed in different realistic data). Finally we describe quantitatively the dynamics out of the stationary state quantifying the power-law slow approach to stability both in single dynamical realization and in average. These results can be generalized to the case of a stochastic increase in the queue length in time with limited fluctuations. As a limit case we recover the situation in which the queue length fluctuates around a constant average value.
authors.affiliation: Dipartimento di Fisica, Centre SMC, INFM-CNR, Università di Roma Sapienza, Piazzale A. Moro 2, 00185 Rome, Italy and ISC, CNR, Via dei Taurini 19, 00185 Rome, Italy.
authors.forename: A
authors.initials: A
authors.lastname: Gabrielli
authors.forename: G
authors.initials: G
authors.lastname: Caldarelli