Randomized Algorithms for Distributed Systems

所提出的研究关注的是分布式计算资源的随机算法的开发和分析。分布式资源可以是紧密或松散连接的计算机的网络、用于灾难响应的自组织网络、传感器网络或简单地一组联合执行任务的通信机器人，例如，探索一些地形。 虽然分布式计算已经存在了很长一段时间，但它和它的一些亲戚最近也在公众眼中变得时髦。 作为主要的驱动力， 数据的非现场存储（例如，谷歌文档或Dropbox的非常主流的应用程序），或现在无处不在的云计算。 目前存在商业大型数据中心， 在存储容量以及处理能力方面。 然而，尽管在奥登网络中的并行代码执行和数据通信的许多方面，包括基本操作， 如负载平衡、调度和路由，都是手工优化的，在新的范例下，这显然不再可行。 该提案建议在分布式计算的三个不同领域进行研究。第一个领域是负载平衡，这里提出的工作是在该地区的球到箱子游戏和扩散负载平衡。 第二个领域是随机游动。随机行走可以用作地形探索的数学模型。在这里，地形是由一个图形建模和机器人（随机行走）被允许移动 沿着图的边缘。 第三个领域是网络中的通信，这里提出的研究涉及信息传播。

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.