1982 年 7 月，莱斯利·兰波特、Robert Shostak 与 Marshall Pease 在 ACM Transactions on Programming Languages and Systems 第 4 卷第 3 期发表《The Byzantine Generals Problem》，页码 382 至 401。

拜占庭容错 · 口头消息 · 签名消息

当代

Lamport 1978：先于关系怎样把分布式事件收成不靠墙钟的偏序

Time, Clocks, and the Ordering of Events in a Distributed System

1978 年 7 月，莱斯利·兰波特（Leslie Lamport）在 Communications of the ACM 第 21 卷第 7 期发表《Time, Clocks, and the Ordering of Events in a Distributed System》，页码 558 至 565。

逻辑时钟 · happened-before · Lamport

当代

FLP：完全异步下一次崩溃也能挡住确定性共识

FLP 1985: Impossibility of Distributed Consensus with One Faulty Process

1985 年 4 月，迈克尔·费希尔（Michael J. Fischer）、南希·林奇（Nancy A. Lynch）与迈克尔·帕特森（Michael S. Paterson）在 Journal of the ACM 第 32 卷第 2 期发表《Impossibility of Distributed Consensus with One Faulty Process》，页码 374 至 382。

FLP · 共识 · 异步

当代

Ben-Or 1983：抛硬币怎样把异步共识的终止改成几乎必然

Ben-Or 1983: Randomized Agreement in Complete Asynchrony

1983 年，迈克尔·本-奥尔（Michael Ben-Or）在 PODC 发表短文《Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols》，页码 27 至 30。

Ben-Or · 随机共识 · FLP

当代

Chandra–Toueg 1996：会犯错的怀疑预言怎样成为共识的最弱检测器

Chandra–Toueg 1996: Unreliable Failure Detectors for Reliable Distributed Systems

1996 年 4 月，图沙尔·迪帕克·钱德拉（Tushar Deepak Chandra）与萨姆·图埃格（Sam Toueg）在 Journal of the ACM 第 43 卷第 2 期发表《Unreliable Failure Detectors for Reliable Distributed Systems》，页码 225 至 267。

Chandra-Toueg · 故障检测器 · 最终弱检测器

当代

Herlihy–Wing 1990：线性化怎样把并发对象收成合法的顺序历史

Linearizability: A Correctness Condition for Concurrent Objects

1990 年 7 月，莫里斯·赫利希（Maurice P. Herlihy）与珍妮特·温（Jeannette M. Wing）在 ACM Transactions on Programming Languages and Systems 第 12 卷第 3 期发表《Linearizability: A Correctness Condition for Concurrent Objects》，页码 463 至 492。

线性化 · Herlihy-Wing · 并发对象

当代

Fidge–Mattern：分量时间戳怎样把并发从标量编号里认出来

Fidge–Mattern: Timestamps That Preserve the Partial Ordering

1988 年，科林·J.·菲奇（Colin J. Fidge）在第 11 届澳大利亚计算机科学会议（University of Queensland）发表《Timestamps in Message-Passing Systems That Preserve the Partial Ordering》，页码 56 至 66；同文亦见于 Australian Computer Science Communications 第 10 卷第 1 期。

向量时钟 · Fidge · Mattern

当代

Garcia-Molina 1982：编号更高的进程怎样在超时假设下抢走协调者

Garcia-Molina 1982: Elections in a Distributed Computing System

1982 年 1 月，赫克托·加西亚-莫利纳（Hector Garcia-Molina）在 IEEE Transactions on Computers 第 C-31 卷第 1 期发表《Elections in a Distributed Computing System》，页码 48 至 59。

bully · 选举算法 · Garcia-Molina

当代

Castro–Liskov 1999：实用拜占庭容错，不是将军寓言

Castro–Liskov 1999: Practical Byzantine Fault Tolerance

1999 年 2 月，米格尔·卡斯特罗（Miguel Castro）与芭芭拉·利斯科夫在新奥尔良第三届 OSDI 上发表《Practical Byzantine Fault Tolerance》，页码 173 至 186，DOI 10.5555/296806.296824。

PBFT · 拜占庭容错 · 状态机复制

当代

Chandy–Lamport 1985：标记消息怎样把全局状态收成一致割

Distributed Snapshots: Determining Global States of Distributed Systems

1985 年 2 月，凯·马尼·钱迪（K. Mani Chandy）与莱斯利·兰波特（Leslie Lamport）在 ACM Transactions on Computer Systems 第 3 卷第 1 期发表《Distributed Snapshots: Determining Global States of Distributed Systems》，页码 63 至 75。

分布式快照 · Chandy-Lamport · 一致割

当代

Gilbert–Lynch 2002：异步网上原子寄存器无法既可用又抗分区

Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

2002 年 6 月，塞思·吉尔伯特（Seth Gilbert）与南希·林奇（Nancy A. Lynch）在 ACM SIGACT News 第 33 卷第 2 期发表《Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services》，页码 51 至 59。

CAP · Gilbert-Lynch · 原子寄存器

当代

Gray 1978：两阶段提交怎样把多处改动收成提交或中止

Notes on Data Base Operating Systems: Two-Phase Commit

1978 年，吉姆·格雷（Jim Gray）的长篇讲义《Notes on Data Base Operating Systems》收入鲁道夫·拜耳（Rudolf Bayer）、罗伯特·格雷厄姆（Robert M. Graham）与格哈德·塞格米勒（Gerhard Seegmüller）主编的 Operating Systems: An Advanced Course，作为 Springer LNCS 第 60 卷印出，页码 393 至 481。

两阶段提交 · 原子提交 · 协调者

当代

Shapiro 2011：副本收敛是半格或可交换操作，不是共识协议

Conflict-free Replicated Data Types

2011 年 10 月，马克·夏皮罗（Marc Shapiro）、努诺·普雷吉萨（Nuno Preguiça）、卡洛斯·巴克罗（Carlos Baquero）与马雷克·扎维尔斯基（Marek Zawirski）在第十三届 Stabilization, Safety, and Security of Distributed Systems（SSS）发表《Conflict-free Replicated Data Types》，收入 Springer LNCS 第 6976 卷，页码 386 至 400。

CRDT · 半格 · 强最终一致性

当代

Dwork–Lynch–Stockmeyer 1988：终将有界的延迟怎样让确定性共识可能

DLS 1988: Consensus in the Presence of Partial Synchrony

1988 年 4 月，辛西娅·德沃克（Cynthia Dwork）、南希·林奇（Nancy A. Lynch）与拉里·斯托克迈尔（Larry Stockmeyer）在 Journal of the ACM 第 35 卷第 2 期发表《Consensus in the Presence of Partial Synchrony》，页码 288 至 323。

部分同步 · GST · 共识

当代

Attiya–Bar-Noy–Dolev 1995：消息传递上的原子寄存器

ABD 1995: Sharing Memory Robustly in Message-Passing Systems

1995 年 1 月，哈吉特·阿蒂亚（Hagit Attiya）、阿莫茨·巴尔-诺伊（Amotz Bar-Noy）与丹尼·多莱夫（Danny Dolev）在 Journal of the ACM 第 42 卷第 1 期发表《Sharing Memory Robustly in Message-Passing Systems》，页码 124 至 142。

ABD · 原子寄存器 · 多数派

当代

Herlihy 1991：等待自由怎样按共识数给并发对象分层

Wait-Free Synchronization

1991 年 1 月，莫里斯·赫利希（Maurice P. Herlihy）在 ACM Transactions on Programming Languages and Systems 第 13 卷第 1 期发表《Wait-Free Synchronization》，页码 124 至 149。

等待自由 · 共识数 · Herlihy

当代

Herlihy–Moss 1993：事务内存怎样用体系结构支持无锁数据结构

Transactional Memory: Architectural Support for Lock-Free Data Structures

1993 年 5 月，莫里斯·赫利希（Maurice Herlihy）与 J. 艾略特·B. 莫斯（J. Eliot B. Moss）在第 20 届计算机体系结构国际研讨会（ISCA）发表《Transactional Memory: Architectural Support for Lock-Free Data Structures》，页码 289 至 300。

事务内存 · Herlihy-Moss · 无锁

当代

Cook 1971：定理证明手续的复杂度怎样把 SAT 写成 NP 完全

The Complexity of Theorem-Proving Procedures

1971 年 5 月 3 日至 5 日，第三届 ACM 计算理论年会（STOC）在俄亥俄州谢克海茨（Shaker Heights）举行。多伦多大学的斯蒂芬·库克（Stephen A. Cook）发表《The Complexity of Theorem-Proving Procedures》，页码 151 至 158。

Cook-Levin · NP完全 · SAT

当代

Shavit–Touitou 1995：软件事务内存怎样把无锁写成运行时而不是每只对象的手工艺

Software Transactional Memory

1995 年 8 月，尼尔·沙维特（Nir Shavit）与丹·图伊图（Dan Touitou）在第 14 届分布式计算原理研讨会（PODC）发表《Software Transactional Memory》，页码 204 至 213。DOI 为 10.1145/224964.224987。

软件事务内存 · STM · PODC 1995

当代

Karp 1972：组合问题之间的可归约性怎样把二十一个问题写成多项式完全

Reducibility among Combinatorial Problems

1972 年 3 月 20 日至 22 日，国际商用机器公司托马斯·J·沃森研究中心在纽约州约克敦海茨召开「计算机计算的复杂度」讨论会。加州大学伯克利分校的理查德·卡普（Richard M. Karp）发表《Reducibility among Combinatorial Problems》。

Karp · NP完全 · 多一归约

当代

Lamport 1979：顺序一致性怎样把多处理器程序收成某一条尊重程序序的交错

How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs

1979 年 9 月，莱斯利·兰波特（Leslie Lamport）在 IEEE Transactions on Computers 第 C-28 卷第 9 期发表《How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs》，页码 690 至 691。

顺序一致性 · Lamport · 多处理器

当代

Goldwasser–Micali–Rackoff 1985：交互证明系统的知识复杂度怎样把零知识写成定义

The Knowledge Complexity of Interactive Proof-Systems

1985 年 5 月 6 日至 8 日，第十七届 ACM 计算理论年会（STOC）在罗德岛普罗维登斯举行。

GMR · 交互式证明 · 知识复杂度

当代

Hoare 1969：公理基础怎样把程序正确性写成可推导的三元组

An Axiomatic Basis for Computer Programming

1969 年 10 月，《美国计算机学会通讯》（Communications of the ACM）第 12 卷第 10 期发表 C. A. R. 霍尔（Charles Antony Richard Hoare）的《An Axiomatic Basis for Computer Programming》，页码 576 至 580、583。

Hoare三元组 · 赋值公理 · 推论规则

当代

Floyd 1967：归纳断言怎样把程序的意义写在流程图的边上

Assigning Meanings to Programs

1966 年 4 月，美国数学会在纽约召开应用数学讨论会，主题是计算机科学的数学方面。卡内基理工学院（Carnegie Institute of Technology）的罗伯特·弗洛伊德（Robert W. Floyd）宣读了《Assigning Meanings to Programs》。

Floyd · 归纳断言 · 流程图

当代

Savitch 1970：非确定性空间怎样被确定性平方空间模拟

Relationships Between Nondeterministic and Deterministic Tape Complexities

1970 年 4 月，《计算机与系统科学杂志》（Journal of Computer and System Sciences）第 4 卷第 2 期刊出沃尔特·萨维奇（Walter J. Savitch）的《Relationships Between Nondeterministic and Deterministic Tape Complexities》，页码 177 至 192。

Savitch定理 · 空间复杂度 · NSPACE

当代

Valiant 1979：积和式怎样把计数写成比判定更硬的类

The Complexity of Computing the Permanent

1979 年，《理论计算机科学》（Theoretical Computer Science）第 8 卷第 2 期刊出莱斯利·瓦利安特（Leslie G. Valiant）的《The Complexity of Computing the Permanent》，页码 189 至 201。

Valiant · 积和式 · 永久式

当代

Yao 1979：分布式计算的复杂度问题怎样把通信写成资源

Some Complexity Questions Related to Distributive Computing

1979 年 4 月 30 日至 5 月 2 日，第十一届 ACM 计算理论年会（STOC）在佐治亚州亚特兰大举行。

Yao · 通信复杂度 · STOC 1979

当代

Dijkstra 1965：互斥怎样在没有仲裁者的共享变量上写成可推理的问题

Solution of a Problem in Concurrent Programming Control

1965 年 9 月，艾兹格·威贝·迪科斯彻（Edsger W. Dijkstra）在 Communications of the ACM 第 8 卷第 9 期发表《Solution of a Problem in Concurrent Programming Control》，整整一页，页码 569。

Dijkstra · 互斥 · 临界区

当代

Peterson 1981：两进程互斥怎样用两面旗与一个 turn 写成短注

Myths About the Mutual Exclusion Problem

1981 年 6 月 13 日，加里·L·彼得森（Gary L. Peterson）在 Information Processing Letters 第 12 卷第 3 期发表《Myths About the Mutual Exclusion Problem》，页码 115 至 116。

Peterson · 互斥 · Dekker

当代

Hartmanis–Stearns 1965：算法复杂度怎样被写成时间可构造的层次

On the Computational Complexity of Algorithms

1965 年 5 月，《美国数学会汇刊》（Transactions of the American Mathematical Society）第 117 卷刊出尤里斯·哈特马尼斯（Juris Hartmanis）与理查德·斯特恩斯（Richard E. Stearns）的《On the Computational Complexity of Algorithms》，页码 285 至 306。

Hartmanis · Stearns · 时间层次

当代

Lamport 1974：面包店算法怎样给互斥加上先来先服务

A New Solution of Dijkstra's Concurrent Programming Problem

1974 年 8 月，莱斯利·兰波特（Leslie Lamport）在 Communications of the ACM 第 17 卷第 8 期发表《A New Solution of Dijkstra's Concurrent Programming Problem》，页码 453 至 455。

Lamport · 面包店算法 · 互斥

当代

Levin 1973：通用顺序搜索怎样把 NP 搜索写成一个万能问题

Universal Sequential Search Problems

1973 年，《Проблемы передачи информации》（《信息传输问题》）第 9 卷第 3 期刊出列昂尼德·列文（Leonid A. Levin）的短讯《Универсальные задачи перебора》。页码 115 至 116。

Levin · NP 完全 · 通用搜索

当代

Knuth 1966：互斥的集体进展怎样仍允许一个人被永远超过

Additional Comments on a Problem in Concurrent Programming Control

1966 年 5 月，唐纳德·厄尔·克努斯（Donald E. Knuth）在 Communications of the ACM 第 9 卷第 5 期发表《Additional Comments on a Problem in Concurrent Programming Control》，页码 321，排到 322 上栏，体裁是半页评论。

Knuth · 互斥 · 饥饿

当代

Immerman–Szelepcsényi 1988：非确定性空间怎样对补运算封闭

Nondeterministic Space is Closed Under Complementation

1988 年 10 月，《SIAM 计算杂志》（SIAM Journal on Computing）第 17 卷第 5 期刊出尼尔·伊默尔曼（Neil Immerman）的《Nondeterministic Space is Closed Under Complementation》，页码 935 至 938。

Immerman · Szelepcsényi · NL

当代

Baker–Gill–Solovay 1975：相对化怎样把对角化挡在 P 对 NP 门外

Relativizations of the P =? NP Question

1975 年 12 月，《SIAM 计算杂志》（SIAM Journal on Computing）第 4 卷第 4 期刊出西奥多·贝克（Theodore Baker）、约翰·吉尔（John Gill）与罗伯特·索洛维（Robert Solovay）的《Relativizations of the P =?

Baker–Gill–Solovay · 相对化 · 神谕

当代

Ladner 1975：若 P 不等于 NP，中间问题怎样必须存在

On the Structure of Polynomial Time Reducibility

1975 年 1 月，《ACM 会刊》（Journal of the ACM）第 22 卷第 1 期刊出理查德·拉德纳（Richard E. Ladner）的《On the Structure of Polynomial Time Reducibility》，页码 155 至 171。

Ladner · NP 中间 · 多项式归约

当代

Razborov–Rudich 1997：自然证明怎样把电路下界挡在伪随机函数门外

Natural Proofs

1997 年 8 月，《计算机与系统科学杂志》（Journal of Computer and System Sciences）第 55 卷第 1 期刊出亚历山大·拉兹博罗夫（Alexander A. Razborov）与史蒂文·鲁迪奇（Steven Rudich）的《Natural Proofs》，页码 24 至 35。

自然证明 · 电路复杂度 · 伪随机

当代

Furst–Saxe–Sipser 1984：常数深度电路怎样算不出奇偶性

Parity, Circuits, and the Polynomial-Time Hierarchy

1984 年 12 月，《数学系统理论》（Mathematical Systems Theory）第 17 卷刊出梅里克·弗斯特（Merrick Furst）、詹姆斯·B·萨克斯（James B. Saxe）与迈克尔·西普塞尔（Michael Sipser）的《Parity, Circuits, and the Polynomial-Time Hierarchy》，页码 13 至 27。

AC0 · 奇偶性 · 电路复杂度

当代

Håstad 1986：切换引理怎样把浅电路收成近乎最优的下界

Almost Optimal Lower Bounds for Small Depth Circuits

1986 年 5 月 28 日至 30 日，第十八届 ACM 计算理论年会（STOC）在加利福尼亚州伯克利举行。约翰·哈斯塔德（Johan Håstad）的《Almost Optimal Lower Bounds for Small Depth Circuits》印在会议录页码 6 至 20。

切换引理 · AC0 · 奇偶性

当代

Karp–Lipton 1980：SAT 若有多项式电路，多项式层次怎样坍到第二层

Some Connections between Nonuniform and Uniform Complexity Classes

1980 年 4 月 28 日至 30 日，第十二届 ACM 计算理论年会（STOC）在洛杉矶举行。

Karp–Lipton · P/poly · 多项式层次

当代

Razborov 1985：单调电路怎样看不见团

Lower bounds on the monotone complexity of some Boolean functions

1985 年，《苏联科学院报告》（Doklady Akademii Nauk SSSR）第 281 卷第 4 期刊出亚历山大·拉兹博罗夫（Alexander A. Razborov）的俄文短讯《Нижние оценки монотонной сложности некоторых булевых функций》，页码 798 至 801。

单调电路 · 团 · 近似方法

当代

Adleman 1978：可放大的随机性怎样被多项式忠告替换

Two Theorems on Random Polynomial Time

1978 年 10 月 16 日至 18 日，第十九届计算机科学基础年会（FOCS）在密歇根州安阿伯举行。会议录页码 75 至 83 刊出伦纳德·阿德尔曼（Leonard M. Adleman）的《Two Theorems on Random Polynomial Time》。

Adleman · BPP · P/poly

当代

Toda 1991：多项式层次怎样被一次

PP is as Hard as the Polynomial-Time Hierarchy

1991 年 10 月，《SIAM 计算杂志》（SIAM Journal on Computing）第 20 卷第 5 期刊出户田诚之助（Seinosuke Toda）的《PP is as Hard as the Polynomial-Time Hierarchy》，页码 865 至 877。

Toda · 户田定理 · PP

当代

Nisan–Wigderson 1994：E 里足够硬的函数怎样冒充 BPP 测试者的硬币

Hardness vs Randomness

1994 年 10 月，《计算机与系统科学杂志》（Journal of Computer and System Sciences）第 49 卷第 2 期刊出诺姆·尼桑（Noam Nisan）与阿维·维格德森（Avi Wigderson）的《Hardness vs Randomness》，页码 149 至 167。

Nisan–Wigderson · 伪随机发生器 · 去随机化

当代

Valiant–Vazirani 1986：唯一可满足性怎样被随机归约钉成和 SAT 一样硬

NP is as easy as detecting unique solutions

1986 年，《理论计算机科学》（Theoretical Computer Science）第 47 卷刊出莱斯利·瓦利安特（Leslie G. Valiant）与维贾伊·瓦齐拉尼（Vijay V. Vazirani）的《NP is as easy as detecting unique solutions》，页码 85 至 93。

Valiant–Vazirani · 隔离引理 · Unique SAT

当代

Impagliazzo–Wigderson 1997：E 的指数电路硬度怎样把 BPP 收成 P

P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma

1997 年 5 月 4 日至 6 日，第二十九届 ACM 计算理论年会（STOC）在得克萨斯州埃尔帕索举行。

Impagliazzo–Wigderson · 去随机化 · BPP

当代

Yao 1982：陷门函数怎样把单向置换的硬度放大成假硬币

Theory and Application of Trapdoor Functions

1982 年 11 月 3 日至 5 日，第二十三届计算机科学基础年会（FOCS）在伊利诺伊州芝加哥举行。会议录页码 80 至 91 刊出姚期智（Andrew C. Yao）的《Theory and Application of Trapdoor Functions》。

Yao · 陷门函数 · XOR引理

当代

Goldreich–Levin 1989：每个单向函数都有一枚内积硬核谓词

A Hard-Core Predicate for all One-Way Functions

1989 年 5 月 15 日至 17 日，第二十一届 ACM 计算理论年会（STOC）在华盛顿州西雅图举行。

Goldreich–Levin · 硬核谓词 · 单向函数

当代

Blum–Micali 1984：离散对数硬核怎样迭代成密码学伪随机比特

How to Generate Cryptographically Strong Sequences of Pseudorandom Bits

1984 年 11 月，《SIAM Journal on Computing》第 13 卷第 4 期刊出曼纽尔·布卢姆（Manuel Blum）与西尔维奥·米卡利（Silvio Micali）的《How to Generate Cryptographically Strong Sequences of Pseudorandom Bits》，页码 850 至 864。

Blum–Micali · 伪随机发生器 · 硬核谓词

当代

Impagliazzo 1995：略微难的问题怎样收成一块几乎乱猜的硬核分布

Hard-Core Distributions for Somewhat Hard Problems

1995 年 10 月 23 日至 25 日，第三十六届计算机科学基础年会（FOCS）在威斯康星州密尔沃基举行。

Impagliazzo · 硬核分布 · 硬核集合

当代

Impagliazzo–Levin–Luby 1989：一般单向函数怎样交出多项式时间伪随机发生器

Pseudo-random Generation from One-way Functions

1989 年 5 月 15 日至 17 日，第二十一届 ACM 计算理论年会（STOC）在华盛顿州西雅图举行。

Impagliazzo–Levin–Luby · 伪随机发生器 · 单向函数

当代

Goldwasser–Micali 1984：语义安全怎样把密文写成多项式不可区分

Probabilistic Encryption

1984 年 4 月，《计算机与系统科学杂志》（Journal of Computer and System Sciences）第 28 卷第 2 期刊出沙菲·戈德瓦塞尔（Shafi Goldwasser）与西尔维奥·米卡利（Silvio Micali）的《Probabilistic Encryption》，页码 270 至 299。

Goldwasser–Micali · 概率加密 · 语义安全

当代

Goldreich–Goldwasser–Micali 1986：长度翻倍发生器怎样铺成询问下仍像随机的函数

How to Construct Random Functions

1986 年 10 月，《Journal of the ACM》第 33 卷第 4 期刊出奥德·戈德赖希（Oded Goldreich）、沙菲·戈德瓦塞尔（Shafi Goldwasser）与西尔维奥·米卡利（Silvio Micali）的《How to Construct Random Functions》，页码 792 至 807。

Goldreich–Goldwasser–Micali · 伪随机函数 · GGM 树

当代

Diffie–Hellman 1976：公钥怎样把陷门、指数与签名写成公开程序

New Directions in Cryptography

1976 年 11 月，《IEEE 信息论汇刊》（IEEE Transactions on Information Theory）第 22 卷第 6 期刊出惠特菲尔德·迪菲（Whitfield Diffie）与马丁·E·赫尔曼（Martin E. Hellman）的《New Directions in Cryptography》，页码 644 至 654。

Diffie–Hellman · 公钥密码学 · 陷门单向函数

当代

Luby–Rackoff 1988：伪随机函数怎样三轮费斯托变成询问下仍像随机的置换

How to Construct Pseudorandom Permutations from Pseudorandom Functions

1988 年 4 月，《SIAM Journal on Computing》第 17 卷第 2 期刊出迈克尔·卢比（Michael Luby）与查尔斯·拉科夫（Charles Rackoff）的《How to Construct Pseudorandom Permutations from Pseudorandom Functions》，页码 373 至 386。

Luby–Rackoff · 伪随机置换 · 费斯托网络

当代