守住发际线：南大蒋炎岩谈读博那些事儿(9)

因此在这里必须劝退一波想要「通过读个博士过上安逸日子」的人，这条路越来越行不通了。如果你还没有被劝退，恭喜你！读博的经历是独一无二的，如果当了一个社畜 (我曾经有过无数当社畜的机会)，就不会有那么多精彩的发现了。
简短的致谢
走上计算机科学的道路多多少少算是件「命中注定」的事，大概要从幼儿园起相爱相杀的基友彭泱 (Richard Peng) 开始吧。他是个非常神奇的人物：记忆力超强、解题速度超快、受到的训练超好。这个基本上是我能见到的「天花板」，虽然如他所说，做数学的人更可怕，不过好像那些人并不在我生活的世界里。然后一路都遇到很多有趣的人 (无法一一致谢)，包括大学时代一起参加 ACM-ICPC 的队友李昂和李珅，度过了非常愉快美好的本科时光，在美国重逢的时候还一起旅游了一场 Regional (说好的 AK 变成了各种 WA 到死)。到读博期间，我的导师们 (吕校长、马所长、许畅和秦锋老师) 都非常支持我，给了我超棒的研究环境，甚至有时候都不好意思差遣我当马仔，我自己是觉得不太好意思的 (我有一个做马仔的觉悟，但好像也许因为自己有同学多做了一些马仔活)。
一段精彩的生活告一段落，谨此纪念。
p.s. 感谢老板许畅在文中标注的「老板内心独白」。
高能预警：以下是技术内容可以忽略
附录：我到底做了个啥玩意？
从「哲♂学家吃饭」问题说起
从某种意义上来说，博士期间我是研究哲 ♂ 学的。「哲学家吃饭问题」是大学时代学习并发编程时的经典难题。现在哲学家们受到盛情的邀请来到舌尖上的中国，面对一桌丰盛的菜肴，他们不再受限于必须同时拿起手边的两根筷子才能用餐，因此可以更尽兴地享用美食。另一方面，吃中餐的哲学家们也带来了一个新的问题——聚餐是一个很复杂的过程，我们能否把吃饭时发生的事情像讲故事一样，完整地复述出来？
如果把哲学家看作是线程，每道菜看作是变量，那么每个哲学家在吃饭的过程中都可以多次执行以下两个操作：(1) 观察某一道菜，在瞬间记下这道菜的模样 (相当于读出变量的值)；(2) 吃某一道菜，在瞬间改变它的模样 (相当于为某个变量写入一个值)。哲学家们都是了不起的天才，在吃饭的过程中都已默默地记下自己所知的一切，即每个线程记录下自身发生的读/写操作的变量和它们的数值。
之后的一天，哲学家们重新聚在一起，试图解决「哲学家吃中餐问题」：他们各自整理了对那一天吃饭过程的记忆，并试图一起还原出吃饭的完整过程。更确切地说，我们希望在程序执行结束后，把线程本地的读/写操作日志合并成全局的变量读/写序列，相当于给所有读/写事件分配发生的先后次序，使得每个读事件读出的数值都等于最近一次对该变量写入事件写入的数值（即根据线程本地日志得到全局满足顺序一致性的事件排序），如图 1 所示。Gibbons 和 Korach 在 1997 年对于「哲学家吃中餐问题」给出了一个颇为悲观的答案 [1]：如果 P ≠ NP，再聪明的哲学家也无法在多项式时间里恢复出满足顺序一致性的事件排序。甚至，即便哲学家吃的是火锅 (只有一道菜，即一个变量的情形)，NP-完全性也是成立的。