PODC2018会议简介

[2020.6.10补充] 我们后来的一份工作在PODC2020发表。arxiv版本见：https://arxiv.org/abs/2001.07855

[注] 我们的一份工作以短文的形式发表在PODC2018，第一作者魏恒峰去参加了此次会议。应《CCF通讯》邀稿，我们为“顶级国际会议简介”专栏写了一篇介绍PODC2018会议的文章。预计正式发表时会有所修改。

分布式计算原理会议（ACM Symposium on Principles of Distributed Computing）是分布式计算领域的国际顶级学术会议，也是中国计算机学会（CCF）推荐的B类国际学术会议。

分布式计算原理会议开始于1982年，每年一届，今年是第37届。今年的 PODC会议于7月23日至7月27日在英国伦敦大学皇家霍洛威学院（Royal Holloway, University of London）举行。其中，首尾两天各安排了三场专题研讨会（workshop）和两场教学讨论班（tutorial）。为了庆祝Jennifer Welch六十岁生日，会议还于7月23日安排了四场演讲，讨论了Jennifer Welch在分布式计算领域所做的重要贡献及其影响。报告人包括Jennifer Welch的导师Nancy Lynch与合作者Hagit Attiya、Shlomi Dolev与Nitin Vaidya。

• Dijkstra奖

Dijkstra奖创立于2000年，每年一届，授予在分布式计算领域做出突出贡献的学者。Dijkstra奖原为PODC有影响力论文奖（PODC Influential-Paper Award)。2002年，Edsger W. Dijkstra因在Self-Stabilization理论上所做出的开创性贡献获得该奖项，但于同年不幸因病逝世。为了纪念这位卓越的计算机科学家，该奖项于次年更名为Dijkstra奖。2007年起，Dijkstra奖由 PODC会议和DISC（International Symposium on DIStributed Computing）会议共同资助，颁奖仪式也改为在这两个会议上轮流举行（偶数年份在PODC会议，奇数年份在DISC会议）。

今年的Dijkstra奖授予了Bowen Alpern和Fred B. Schneider，获奖论文是1985年发表在“Information Processing Letters”上的“Defining Liveness”。该论文仅有5页，但却具有重要的理论意义。Leslie Lamport在1977年的一篇论文中提出了Safety（安全性）和Liveness（活性）概念，用以刻画并发程序的特性。直观地讲，Safety表示“坏事”不会发生，而Liveness表示“好事”确会发生。但是，Leslie Lamport没能给出Liveness的形式化定义。该获奖论文的一大贡献便是给出了Liveness的形式化定义。不仅如此，该论文还从拓扑的角度证明了任何定义在系统执行之上的特性（称为trace property）都可以表示成一个Safety特性和一个Liveness特性之交。这个简洁、优雅的定理一方面加强了Safety和Liveness定义的直观性与合理性，另一方面也指出了Safety和Liveness具有本质区别。论文中的这些经典结果在后续的分布式计算领域以及形式化方法领域中都产生了深远的影响。

颁奖仪式在7月25日的晚宴上举行。两位作者在获奖演讲中回顾了论文产生的背景和过程。有趣的是，Fred B. Schneider提到他们曾将相关论文投稿到PODC，但是被拒了。感兴趣的读者可以到Fred B. Schneider 的主页上阅读他的演讲草稿（也可联系作者魏恒峰获取演讲录音）。

• PODC博士论文奖

今年的PODC博士论文奖（Doctoral Dissertation Award）颁给了来自 MIT的Rati Gelashvili博士。在博士论文“On the Complexity of Synchronization”中，作者深入研究了分布式算法中的经典同步任务的复杂度。该论文的贡献之一是指出了使用Consensus Number刻画并发原语的计算能力这一传统方法的局限性，并提出了一种新的刻画方法。

Rati Gelashvili 博士的导师Nir Shavit教授是2012年Dijkstra奖的获得者，并曾与Maurice Herlihy一起获得2004年的Gödel奖。Consensus Number正是Maurice Herlihy的代表性工作之一。

• PODC最佳论文奖

今年的PODC最佳论文奖（Best Paper Award）的获得者是Leonid Barenboim、Michael Elkin和Uri Goldenberg，获奖论文是“Locally-Iterative Distributed ( )-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models”。该论文解决了分布式图着色算法中长达25年悬而未决的重要问题。

今年的PODC最佳学生论文奖（Best Student Paper Award）由两篇论文分享：一篇题为“Silence”，作者是Guy Goren与Yoram Moses（2009年Dijkstra奖获得者、1997年Gödel奖获得者）。该论文首次严格地分析了在同步模型下如何通过不发送消息来传递信息。另一篇论文的题目是“An Asynchronous Computability Theorem for Fair Adversaries”，作者是Thibault Rieutord与Yuan He。该论文从拓扑的角度刻画了一类分布式计算模型的计算能力。

分布式计算理论是建立在计算模型之上的，包括时间模型、通信模型、故障模型等。模型与问题、方法以及技术紧密相关。在分布式计算理论兴起的初期阶段，就有各种各样的计算模型。随着分布式系统的应用越来越广泛，新的模型更是层出不穷，分布式计算理论也因此不断焕发新的生机。

• 经典分布式计算模型与问题仍是研究重点

Consensus问题（Session 2D: Consensus）

Consensus 是分布式计算理论中的核心问题。针对不同的计算模型，研究人员一直在努力提高Consensus算法的效率或者探索Consensus问题本身的难度。根据著名的FLP定理，在异步模型下，不存在确定性的、具有容错能力且满足wait-free性质的Consensus算法。为了绕开这个不可能性定理，研究人员开始考虑随机算法或者非严格（exact）的Consensus问题。论文“Almost-Surely Terminating Asynchronous Byzantine Agreement Revisited”提出了两个具有不同期望消息复杂度的随机算法，它们能容忍不同数量的Byzantine进程。论文“Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics”为已知的两个随机Byzantine Consensus算法提供了更紧的复杂度分析结果。论文“Tight Bounds for Asymptotic and Approximate Consensus”则研究了两类非严格的Consensus问题的难度。
与Consensus问题密切相关的AC（Atomic Commitment）问题也是研究重点。今年的一篇最佳学生论文“Silence”利用同步模型下通过silence（即不发送消息）传递信息的能力将AC协议的消息复杂度从多项式级别降到了常数级别。

并发理论（Session 3B: Concurrency）

并发理论是多个领域共同的研究热点，如分布式计算领域、多处理器领域、数据库领域、程序设计语言领域等。论文“Locking Timestamps versus Locking Objects”关注传统的数据库事务处理问题，提出了“为时间戳上锁而不是为对象上锁”的基本思想，并据此设计了一类新的多版本并发控制协议。论文“Relaxed Schedulers Can Efficiently Parallelize Iterative Algorithms”考察了非严格的（relaxed）调度器对迭代算法的并行度的影响。结果表明存在一类非严格的调度器可以高效地执行某些经典的迭代算法，例如求极大独立集或者极大匹配的贪心算法。另有两篇短文（属于Brief Announcement）关注并发数据结构与并发算法的性能。

共享内存理论（Session 1B: Shared Memory Theory）

经典的进程通信模型有两种，一种是消息传递模型，另一种是共享内存模型。在共享内存模型中，多个进程通过访问共享对象进行通信，而无需关心更底层的消息传递细节。因此，共享内存模型具有抽象层次高、易于理解、易于使用等特点。Hagit Attiya等人的论文“Separating Lock-Freedom from Wait-Freedom”关注共享内存模型中的一个由来已久的重要理论问题：是否所有的可以用lock-free方式实现的共享对象都存在wait-free的算法？对此，该论文给出了否定的回答。这意味着lock-freedom与wait-freedom有着本质区别。Faith Ellen等人的论文“Revisionist Simulations: A New Approach to Proving Space Lower Bounds”研究共享内存模型中的空间复杂度问题。具体而言，论文给出了解决 -obstruction-free -set agreement 问题所需共享读写寄存器（read/write register）数量的下界，这是对已知下界结果的重大改进。论文“On the Classification of Deterministic Objects via Set-Agreement Power”研究Set-Agreement问题是否能完全刻画确定性共享对象的计算能力。对此，论文给出了否定的回答。论文“Passing Messages while Sharing Memory”则另辟蹊径，将两种经典的通信模型融合起来，提出了一种混合通信模型。通过解决经典的Consensus问题与Leader Election问题，论文展现了混合模型相对于单个模型在可扩展性、容错性以及对异步的容忍性等方面的优势。

• 分布式图算法是近年来的研究热点

分布式图算法一直以来都是分布式计算领域的研究重点，尤其是近几年，更是成为一大研究热点。今年的PODC会议议程中至少有四个以分布式图算法为主题的Sessions，涉及的图算法问题包括极大独立集、图匹配、顶点覆盖、点着色、最短路径、图的直径、平面图判定、最小割、最小生成树等。

不少论文在解决分布式图算法问题时都采用了经典的CONGEST模型。Keren Censor-Hillel在主题报告“Barriers due to Congestion and Two Ways to Deal With Them”中总结了在CONGEST模型下证明分布式图算法问题的复杂度下界的技术，并通过示例说明了适当放松对解的要求有可能大幅降低通信代价。此次会议还安排了“Session 3A: Congest”专门讨论CONGEST模型下的分布式图算法问题。

在今年的PODC会议上，分布式图算法中的着色问题得到了广泛关注。“Session 3C: Coloring”中包含三份工作。论文“Distributed Coloring in Spare Graphs with Fewer Colors”首先提出了使用六种颜色在 （ 表示顶点数目）轮内对平面图进行着色的分布式算法，然后将该算法扩展到稀疏图上，最后还证明了不存在使用四种颜色在 轮内对平面图进行着色的分布式算法。论文“Improved Distributed Delta-Coloring”针对最大顶点度 的不同取值设计了两个随机算法，降低了已保持25年的问题上界。今年的最佳论文“Locally-Iterative Distributed ( )-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models”提出了一类低于Szegedy-Vishwanathan界限的分布式图着色算法，并将其应用到多种不同图算法问题和模型中。

• 新技术催生新模型与新理论

区块链（Session 2C: Security, Blockchains, and Replication）

区块链技术并非起源于分布式计算领域，但是正如Maurice Herlihy在PODC2017会议主题报告中指出的那样，围绕区块链技术产生的很多问题——比如Consensus、数据复制（replication）、容错、隐私、安全等——都是分布式计算领域中的经典问题。Maurice Herlihy在今年的PODC论文“Atomic Cross-Chain Swaps”中定义了跨链原子交换问题，确立了问题模型，给出了问题是否可解的条件，并在可解情况下设计了交换协议。Ali Schoker在短文“Brief Announcement: Sustainable Blockchains through Proof of eXercise”中提出了Proof of eXercise（PoX）的概念。基于Proof of Work（PoW）概念的区块链技术要求矿工（miner）解决一个“无用的”密码学谜题（cryptographic puzzle），这是对计算资源的一种浪费。PoX要求解决的则是“有用的”基于矩阵的科学计算问题。
此外，在今年的PODC会议期间，Maurice Herlihy等人还组织了一场为期一天的关于区块链技术与理论的专题研讨会（workshop）。

持久性内存（Session 1A: Persistent Memory）

Robert Peglar在主题报告“Overview of Persistent Memory in Distributed Systems Architecture —— Past, Present, Future”中回顾了基于持久性内存的系统设计的历史，讨论了在分布式系统中使用持久性内存的方法和问题，然后指出了在大规模多处理器系统中使用持久性内存的挑战与机遇。
非易失性（non-volatile）内存或持久性（persistent）内存技术给分布式计算领域中的传统问题提出了新的挑战。Hagit Attiya等人在论文“Nesting-Safe Recoverable Linearizability: Modular Constructions for Non-Volatile Memory”中针对非易失性内存提出了抽象的单进程故障恢复模型，并为可恢复并发对象提出了新的正确性条件（correctness condition）。Wojciech Golab 与Danny Hendler在论文“Recoverable Mutual Exclusion Under System-Wide Failures”中研究了可恢复互斥（recoverable mutual exclusion）问题的时间复杂度。短文“Brief Announcement: Persistent Multi-Word Compare-and-Swap”为针对持久性内存的基本并发原语CAS（compare-and-swap）设计了更为高效的算法。

中国学者与PODC会议

根据我们的统计，自2010年以来，有中国高校或研究机构参与完成的 PODC论文共计13篇，其中长文（regular paper类型）9篇，短文（brief announcement 类型）4篇。（由于部分论文的作者是以姓氏排序的，我们未采用只看“第一作者”的标准。）9篇长文分别来自南京大学（3篇）、清华大学（２篇）、天津大学（１篇）、浙江大学与香港大学（合作１篇）、香港科技大学（１篇）以及（台湾）中央研究院（１篇）。4篇短文分别来自北京大学（１篇）、南京大学（１篇）、国防科技大学（1篇）以及浙江大学与华中科技大学（合作１篇）。该统计结果在一定程度上反映了中国学者在分布式计算基础理论方面的研究还有待加强。

南京大学计算机科学与技术系助理研究员。
主要研究方向为分布式计算（目前主要关注数据一致性问题）、形式化方法。
hfwei at nju dot edu dot cn

南京大学计算机科学与技术系教授。
主要研究方向为分布式算法设计与分析、分布式系统实现与验证。
yuhuang at nju dot edu dot cn