## The Impact of Randomisation in Load Balancing and Random Walks

## Repository URI

## Repository DOI

## Change log

## Authors

## Abstract

The real world is full of uncertainties. Classical analyses usually favour deterministic cases, which in practice can be too restricted. Hence it motivates us to add in randomness to make models similar to practical situations. In this thesis, we mainly study two network problems taken from the distributed computing world: iterative load balancing and random walks. An interesting observation is that the problems we study, though not quite related regarding their real world applications, can be linked by the same mathematical toolkit: Markov chain theory. These problems have been heavily studied in the literature. However, their assumptions are mostly \emph{deterministic}, which causes less flexibility and generality to the real world settings. The novelty of this thesis is that we add randomness in these problems in order to observe worst cases vs. average cases (load balancing) and static cases vs. dynamic cases (random walks).

For iterative load balancing, the randomness is added on the number of tasks over the entire network. Previous works often assumed worst case initial loads, which may be wasteful sometimes. Hence we relax this condition and assume the loads are drawn from different probability distributions.

In particular, we no longer assume the initial loads are chosen by an adversary. Instead, we assume the initial loads on each processor are sampled from independent and identically distributed (i.i.d.) probability distributions. We then study the same problems as in classical settings, i.e., the time needed for the load balancing process to reach a sufficiently small discrepancy.

Our main result implies that under such a regime, the time required to balance a network can be much faster. An insightful observation is that the load discrepancy is proportional to the term

For random walks, the randomness is added on the network topologies. This means at each time step (considering discrete times), the underlying network can change randomly. In particular, we want the graph ``evolves'' instead of changing arbitrarily. To model the graph changing process, we adopt a model commonly used in the literature, i.e., the edge-Markovian model. If an edge does not exist between the two nodes, then it will appear in the next step with probability

Our main contributions regarding random walks include the following results. First, we divided the edge-Markovian graph model into different regimes in a parameterised way. This provides an intuitive path to similar analyses of dynamic graph models. Dynamic models are often hard to analyse in the field because of its complicated nature. We present a possible strategy to reach some feasible solutions by using parameters (

## Description

## Date

## Advisors

Zanetti, Luca