We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham e-Theses
You are in:

Randomised Algorithms on Networks

MESHKINFAMFARD, SEPEHR (2016) Randomised Algorithms on Networks. Doctoral thesis, Durham University.

PDF - Accepted Version


Networks form an indispensable part of our lives. In particular, computer networks have ranked amongst the most influential networks in recent times. In such an ever-evolving and fast growing network, the primary concern is to understand and analyse different aspects of the network behaviour, such as the quality of service and efficient information propagation. It is also desirable to predict the behaviour of a large computer network if, for example, one of the computers is infected by a virus. In all of the aforementioned cases, we need protocols that are able to make local decisions and handle the dynamic changes in the network topology. Here, randomised algorithms are preferred because many deterministic algorithms often require a central control. In this thesis, we investigate three network-based randomised algorithms, threshold load balancing with weighted tasks, the pull-Moran process and the coalescing-branching random walk. Each of these algorithms has extensive applicability within networks and computational complexity within computer science.
In this thesis we investigate threshold-based load balancing protocols. We introduce a generalisation of protocols in [2, 3] to weighted tasks.

This thesis also analyses an evolutionary-based process called the death-birth update, defined here as the Pull-Moran process. We show that a class of strong universal amplifiers does not exist for the Pull-Moran process. We show that any class of selective amplifiers in the (standard) Moran process is a class of selective suppressors under the Pull-Moran process. We then introduce a class of selective amplifiers called Punk graphs.

Finally, we improve the broadcasting time of the coalescing-branching (COBRA) walk analysed in [4], for random regular graphs. Here, we look into the COBRA approach as a randomised rumour spreading protocol.

Item Type:Thesis (Doctoral)
Award:Doctor of Philosophy
Keywords:randomised algorithms, networks, Markov chains, random walks, Balls into Bins games, Recourse-Based Model, User-Based Model, load balancing with migration, Weighted Tasks, Threshold load balancing with weighted tasks, recourse-controlled migration, user-controlled migration, above average threshold, tight threshold, evolutionary dynamics, pull-Moran Process, Moran process, death-birth, birth-death, amplifiers, suppressors, selective amplifiers, selective suppressors, the Bridge Thermal Theorem, the Bridge Isothermal Theorem, the Punk graph, coalescing-Branching walk, COBRA walks, expander graphs, random regular graphs, COBRA push, COBRA pull, COBRA push-pull, rumour spreading, rumor spreading, conductance, vertex expansion, Randomized
Faculty and Department:Faculty of Science > Engineering and Computing Science, School of (2008-2017)
Thesis Date:2016
Copyright:Copyright of this thesis is held by the author
Deposited On:31 Mar 2016 10:31

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitter