Distributed algorithms for resource allocation and routing

In this thesis, we study distributed algorithms in the context of two fundamental problems in distributed systems, resource allocation and routing. Resource allocation studies how to distribute workload evenly to resources. We consider two different resource allocation models, the diffusive load balancing and the weighted balls-into-bins games. Routing studies how to deliver messages from source to estination efficiently. We design routing algorithms for broadcasting and gossiping in ad hoc networks. Diffusive load balancing studies how nodes with initial tasks in a network balance their loads concurrently with all their neighbours. We propose a novel analytical method to deal with the concurrent load balancing actions, which are the major obstacle for the analysis. The idea is to first sequentialize the concurrent load balancing actions, analyze this sequential system instead, and then bound the gap between both. We analyze various diffusive load balancing algorithms using this idea. The weighted balls-into-bins game studies how to evenly allocate a set of independent weighted balls into a set of bins. In particular, we consider two different scenarios, the static sequential game and the selfish reallocation game. In the static sequential game, balls come one after another and need to be allocated in such order. We study how the outcome of the game, the expected maximum load of any bin, is influenced by the game parameters such as the distribution of ball weights and the order that balls are allocated. In the selfish reallocation game, every ball has its own initial location. An iterative, selfish distributed reallocation algorithm is applied to balance the workload. We show bounds for the convergence time of the algorithm, which is the number of steps to reach (or get close to) some equilibrium state. We study routing algorithms for broadcasting and gossiping in ad hoc networks. We consider the so-called ``energy efficient" ad hoc network model. Our goal is to minimize not only broadcasting/gossiping time, but also energy consumption, which is measured by the total number of sent messages. We present and analyze several energy efficient broadcasting/gossiping algorithms for both random and general ad hoc networks.