Algorithms and models for distributed systems

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

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).