Load balancing via random local search in closed and open systems

In this paper, we analyze the performance of random load resampling and migration strategies in parallel server systems. Clients initially attach themselves to an arbitrary server, but may switch servers independently at random instants of time in an attempt to improve their service rate. This approach to load balancing contrasts with traditional approaches where clients make smart server selections upon arrival (e.g., Join-the-Shortest-Queue policy and variants thereof). Load resampling is particularly relevant in scenarios where clients cannot predict the load of a server before being actually attached to it. An important example is in wireless spectrum sharing where clients try to share a set of frequency bands in a distributed manner. We first analyze the natural Random Local Search (RLS) strategy. Under this strategy, after sampling a new server randomly, clients only switch to it if their service rate is improved. In closed systems, where the client population is fixed, we derive tight estimates of the time it takes under RLS strategy to balance the load across servers. We then study open systems where clients arrive according to a random process and leave the system upon service completion. In this scenario, we analyze how client migrations within the system interact with the system dynamics induced by client arrivals and departures. We compare the load-aware RLS strategy to a load-oblivious strategy in which clients just randomly switch server without accounting for the server loads. Surprisingly, we show that both load-oblivious and load-aware strategies stabilize the system whenever this is at all possible. We use large-system asymptotics to characterize system performance, and augment this with simulations, which suggest that the average client sojourn time under the load-oblivious strategy is not considerably reduced when clients apply smarter load-aware strategies.     

Bayesian network management

We formulate some general network (and risk) management problems in a Bayesian context, and point out some of the essential features. We argue and demonstrate that, when one is interested in rare events, the Bayesian and frequentist approaches can lead to very different strategies: the former typically leads to strategies which are more conservative. We also present an asymptotic formula for the predictive probability of ruin (for a random walk with positive drift) for large initial capital and large number of past observations. This is a preliminary investigation which raises many interesting questions for future research. This revised version was published online in June 2006 with corrections to the Cover Date.     

Probabilistic consensus via polling and majority rules

In this paper, we consider lightweight decentralised algorithms for achieving consensus in distributed systems. Each member of a distributed group has a private value from a fixed set consisting of, say, two elements, and the goal is for all members to reach consensus on the majority value. We explore variants of the voter model applied to this problem. In the voter model, each node polls a randomly chosen group member and adopts its value. The process is repeated until consensus is reached. We generalise this so that each member polls a (deterministic or random) number of other group members and changes opinion only if a suitably defined super-majority has a different opinion. We show that this modification greatly speeds up the convergence of the algorithm, as well as substantially reducing the probability of it reaching consensus on the incorrect value.     

How to distribute antidote to control epidemics

We give a rigorous analysis of variations of the contact process on a finite graph in which the cure rate is allowed to vary from one vertex to the next, and even to depend on the current state of the system. In particular, we study the epidemic threshold in the models where the cure rate is proportional to the degree of the node or when it is proportional to the number of its infected neighbors. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Non-Parametric Change-Point Estimation using String Matching Algorithms

Given the output of a data source taking values in a finite alphabet, we wish to estimate change-points, that is times when the statistical properties of the source change. Motivated by ideas of match lengths in information theory, we introduce a novel non-parametric estimator which we call CRECHE (CRossings Enumeration CHange Estimator). We present simulation evidence that this estimator performs well, both for simulated sources and for real data formed by concatenating text sources. For example, we show that we can accurately estimate the point at which a source changes from a Markov chain to an IID source with the same stationary distribution. Our estimator requires no assumptions about the form of the source distribution, and avoids the need to estimate its probabilities. Further, establishing a fluid limit and using martingale arguments.