Randomized Algorithms for Distributed Systems

点击翻译按钮获取中文摘要

The proposed research concerns itself with the development and analysis of randomised algorithms for distributed computational resources. The distributed resources can be networks of closely or loosely connected computers, ad-hoc networks for disaster response, sensor networks, or simply a set of communicating robots that jointly perform a task, e.g., exploring some terrain. Whilst distributed computing has been around for a very long time it and a few of its relatives have more recently become fashionable also in the public eye. As the main driving forces are to be considered off-site storage of data (e.g., Google docs or Dropbox for very mainstream applications), or the now ubiquitous Cloud computing. At present there exist commercial large-scale data centres, large-scale with respect to storage capacity as well processing power. However, whilst in the olden days many aspects of parallel code execution and data communication in networks, including primitive operations like load balancing, scheduling and routing, were hand-optimised, under the new paradigms this is clearly not feasible any more. The proposal suggests research in three different areas of distributed computing. The first area is load balancing and here the proposed work is in the area of balls-into-bins games and diffusion load balancing. The second area is random walks. Random walks can be used as a mathematical model for terrain exploration. Here the terrain is modelled by a graph and the robots (random walks) are allowed to move along the edges of the graph. The third area is communication in networks, and here the proposed research is concerned with information spreading.