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 , 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|
|Copyright:||Copyright of this thesis is held by the author|
|Deposited On:||31 Mar 2016 10:31|