Alessandro Panconesi and Aravind Srinivasan, who received their doctorates from Cornell CS under the supervision of David Shmoys, have been awarded the 2019 Edsger W. Dijkstra Prize in Distributed Computing for their paper “Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds.”
Alessandro Panconesi和Aravind Srinivasan在David Shmoys的指导下获得了康奈尔CS的博士学位，他们的论文“通过Chernoff-Hoefffding边界的扩展随机分布边缘着色”获得了2019年Edsger W.Dijkstra分布式计算奖。
The prize is name in honor of Edsger W. Dijkstra (1930-2002), a Dutch systems analyst and pioneer in distributed computing. Indeed, he has had an outsized impact on research in principles of distributed computing. As the IEEE Computer Society notes: “Among his contributions to computer science is the shortest path-algorithm, also known as Dijkstra’s algorithm; Reverse Polish Notation and related Shunting yard algorithm; the THEmultiprogramming system; Banker’s algorithm; and the semaphore construct for coordinating multiple processors and programs.” They also emphasize that Dijkstra innovated the concept of “self-stabilization,” which is understood as “an alternative way to ensure the reliability of the system.”
这个奖项是为了纪念Edsger W. Dijkstra （1930-2002），一位荷兰系统分析员和分布式计算的先驱。事实上，他对分布式计算原理的研究产生了巨大的影响。正如IEEE计算机协会指出的：“他对计算机科学的贡献包括最短路径算法，也被称为dijkstra算法；反向波兰符号和相关的调车场算法；多编程系统；银行家算法；以及用于协调多个处理器和程序的信号量结构。“他们还强调，Dijkstra创新了“自我稳定”的概念，这被理解为“确保系统可靠性的另一种方法”。
The Dijkstra Prize is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory or practice of distributing computing have been evident for at least a decade. The prize is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC).
Dijkstra奖是颁发给那些关于分布式计算原理的杰出论文的，这些论文对分布式计算理论或实践的重要性和影响至少在十年前就已经显现出来了。该奖项由acm分布式计算原理研讨会（podc）和eatcs分布式计算研讨会（disc）联合主办。
Computer Science Professor Fred Schneider was awarded the Dijkstra Prize in 2018, and in 2009 Professor Joseph Halpern received the prize (along with Halpern's former student, Yoram Moses).
计算机科学教授Fred Schneider在2018年获得了Dijkstra奖，2009年Joseph Halpern教授（以及Halpern的以前学生Yoram Moses 也获得了该奖)。
Panconesi is a professor of computer science in the Department of Information at Sapienza, the University of Rome. Srinivasan is a professor of computer science at the University of Maryland, College Park.
Panconesi是罗马大学萨皮恩扎信息系的计算机科学教授。斯里尼瓦桑是马里兰大学帕克分校计算机科学教授。
Lastly, here is an account of Panconesi and Srinivasan’s award-winning work:
最后，以下是Panconesi和Srinivasan获奖作品的介绍：
The paper presents a simple synchronous algorithm in which processes at the nodes of an undirected network color its edges so that the edges adjacent to each node have different colors. It is randomized, using 1.6∆ + O(log1+δ n) colors and O(log n) rounds with high probability for any constant δ > 0, where n is the number of nodes and ∆ is the maximum degree of the nodes. This was the first nontrivial distributed algorithm for the edge coloring problem and has influenced a great deal of follow-up work. Edge coloring has applications to many other problems in distributed computing such as routing, scheduling, contention resolution, and resource allocation.
本文提出了一种简单的同步算法，在无向网络的节点处对其边进行着色处理，使每个节点附近的边具有不同的颜色。它是随机的，对于任何常数δgt；0，使用1.6∏+o（log1+δn）颜色和高概率的o（logn）轮次，其中n是节点数，∏是节点的最大阶数。这是解决边缘着色问题的第一个非平凡的分布式算法，并影响了大量后续工作。边缘着色在分布式计算的路由、调度、竞争解决和资源分配等问题上有着广泛的应用。
In spite of its simplicity, the analysis of their edge coloring algorithm is highly nontrivial. Chernoff–Hoeffding bounds, which assume random variables to be independent, cannot be used. Instead, they develop upper bounds for sums of negatively correlated random variables, for example, which arise when sampling without replacement. More generally, they extend Chernoff–Hoeffding bounds to certain random variables they call λ-correlated. This has directly inspired more specialized concentration inequalities. The new techniques they introduced have also been applied to the analyses of important randomized algorithms in a variety of areas including optimization, machine learning, cryptography, streaming, quantum computing, and mechanism design.
尽管其简单，但对其边缘着色算法的分析是非常重要的。chernoff&ndash；hoefffding界限假定随机变量是独立的，不能使用。相反，他们发展了负相关随机变量之和的上界，例如，当没有替换的抽样时出现的上界。更一般地，它们将chernoff&ndash；hoefffding界扩展到它们称为λ-相关的某些随机变量。这直接激发了更专业化的集中不平等。他们引入的新技术也被应用于分析重要的随机算法，包括优化、机器学习、密码学、流、量子计算和机制设计。
如需进一步了解，或有任何相关疑问，欢迎在线咨询留学专家。如果您对自己是否适合留学还有疑虑，欢迎参与前途出国免费评估，以便给您进行准确定位。
官方小程序
官方公众号
官方微博
百家号
在线时间：7*24小时
