Randomized Algorithms for Distributed Systems

分布式系统的随机算法

• 批准号: 250284-2012
• 负责人: Berenbrink, Petra
• 金额: $ 3.06万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=570873
• 关键词: Randomized; Algorithms; 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.

提出的研究涉及分布式计算资源的随机算法的开发和分析。分布式资源可以是紧密连接或松散连接的计算机网络，用于灾难响应的自组织网络，传感器网络，或者仅仅是一组联合执行任务的通信机器人，例如，探索某些地形。