Algorithms and models for distributed systems

分布式系统的算法和模型

• 批准号: 228091-2011
• 负责人: Ruppert, Eric
• 金额: $ 1.75万
• 依托单位: York University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=634427
• 关键词: Algorithms; models; distributed; systems

For the past 40 years, computer equipment has been steadily growing smaller and faster. Now, however, we are approaching fundamental physical limits that will prevent these improvements from continuing at the same pace. In the future, the way to obtain more computational power will be increased parallelism: computer code will be executed by many "threads" simultaneously and cooperatively to solve a single problem. In 2005, Sutter and Larus announced the "concurrency revolution." They wrote that concurrency will start to play a central role in software development in the near future due to the shift in computer architecture from uniprocessors to multicore processors, which are designed specifically to run many threads on a single chip. The hardware industry has started to invest seriously in the development of multicore processors. Machineswith eight 12-core processors (capable of running 192 threads) will soon be available. Unfortunately, most algorithms designed for uniprocessor systems do not perform well in multicore systems. New techniques are required to design distributed algorithms that take full advantage of the system's parallel capabilities. This is one of the central challenges in the field of computer science today. The main goal of my research is to design and study algorithms in multicore systems for manipulating data structures. (Data structures are the abstract objects that computers use to store and manipulate information.) It is particularly challenging to design data structures that can be accessed and updated by many threads simultaneously: it is difficult to read a data structure while other threads are changing it, and it is still more challenging to maintain consistency of the data when multiple threads update the data structure simultaneously. This work will be complemented by some more theoretical work on complexity lower bounds in distributed computing, and on the impact of anonymity in distributed systems (motivated by scenarios where it is difficult to assign unique identifiers to the processes in a distributed system, or where the processes do not wish to reveal their identities for privacy concerns).

在过去的40年里，计算机设备变得越来越小，越来越快。然而，现在我们正在接近基本的物理极限，这将阻止这些改进以同样的速度继续下去。在未来，获得更多计算能力的方式将是增加并行性：计算机代码将由许多“线程”同时协作执行，以解决单个问题。2005年，Sutter和Larus宣布了“并发革命”。他们写道，由于计算机架构从单处理器向多核处理器的转变，并发将在不久的将来开始在软件开发中发挥核心作用，多核处理器是专门为在单个芯片上运行多个线程而设计的。硬件行业已经开始在多核处理器的开发上投入大量资金。拥有8个12核处理器（能够运行192个线程）的机器将很快面世。不幸的是，大多数为单处理器系统设计的算法在多核系统中表现不佳。需要新的技术来设计分布式算法，以充分利用系统的并行能力。这是当今计算机科学领域的核心挑战之一。我研究的主要目标是设计和研究多核系统中操作数据结构的算法。（数据结构是计算机用来存储和操作信息的抽象对象。）设计可以被多个线程同时访问和更新的数据结构尤其具有挑战性：当其他线程正在更改数据结构时，很难读取数据结构，并且当多个线程同时更新数据结构时，保持数据的一致性更具挑战性。这项工作将由一些关于分布式计算的复杂性下限和分布式系统中匿名影响的更多理论工作来补充（动机是很难为分布式系统中的进程分配唯一标识符，或者进程出于隐私考虑不希望透露其身份）。