Lamport 谈撰写《时间、时钟和分布式系统中事件的排序》
Lamport on writing "Time, Clocks, and the Ordering of Events in a Distributed System"
频道:Turing Awardee Clips · 时长:7:27 · 发布:2020-10-30 · 播放:23951
简介
ACM 和计算机历史博物馆采访的短片,Leslie Lamport 讨论了他撰写关于时间、时钟和事件排序的论文。他解释了其与狭义相对论的联系。
HN 为什么推荐
HN 在分布式系统讨论中引用它作为 Lamport 逻辑时钟背后相对论灵感的主要来源。
那次采访中的这个短片 [0] 值得一看。 — HN, 2024
中文字幕节选
我收到了一份由 Bob Thomas 和 Paul Johnson 撰写的技术报告,内容是关于复制 数据库的,他们在里面提出了一个算法, 当我看到这个算法时,我 意识到它并不完全正确,而不正确的原因 在于它允许系统以某种方式行事, 这种方式似乎违反了因果性,也就是说, 发生在某件事之前的事情, 最终会影响系统,就好像它们是以 相反的顺序发生的一样。我之所以 意识到这一点,与我的背景和对 物理学的兴趣有关。我恰好对 狭义相对论有着非常直观的理解,特别是 Minkowski 在 1908 年那篇著名论文中提出的狭义相对论 的四维时空观。我意识到, 分布式系统中的问题与 物理学中发生的情况非常类似,因为在相对论中, 没有事件全序的概念,因为事件 对于不同的观察者来说,会以不同的顺序出现,但 存在一种两个事件之间的因果序概念,其中一个事件 先于另一个事件,如果对于每个观察者来说,该事件都先于 另一个事件。呃, 基本的定义是,如果你知道一个事件发生在 某个人身上,而另一个事件发生在 另一个人身上,那么就有可能从 第一个人那里发送一条消息或光波,当那个事件发生时,它会在 第二个事件发生之前到达第二个人那里。我意识到,在分布式系统中 有明显的类似物,即一个事件在 一个处理器上发生,先于它在另一个处理器上发生,如果有一条消息或 一系列消息从第一个处理器在这个事件之后开始,并在 他的事件之前到达第二个处理器。这就是 因果性或先于的概念,而在这个算法中它被违反了。我 对算法做了一个相当简单的修改, 呃,来纠正这一点,这就是 那篇论文中提出的算法,以及偏序关系的定义。 我意识到的另一件事,我相信 Johnson 和 Thomas 没有意识到的是, 这个算法不仅适用于任何,呃,不仅适用于分布式 数据库,而是适用于任何事物, 而表达任何事物的方式就是状态机。 我在这篇论文中引入的是用状态机描述系统的概念。 现在,状态机是非常简单的东西,它 从初始状态开始,呃,然后它 采取步骤改变其状态,它接下来能做什么可以取决于 呃,在这种情况下是传入的消息,或者来自环境,或者它可以来自 来自 或者来自机器的当前状态决定了它接下来能做什么,而 我意识到并在那篇论文中说的是,任何系统,你知道,如果它是一个单一的 系统,在某种意义上,它应该做什么可以用状态机来描述,而 你可以用这个算法实现任何状态机,所以你可以解决任何问题。 论文发表的结果是,有些人认为它是关于 事件的偏序,有些人认为它是关于分布式互斥 的,几乎没有人认为它是关于状态机的。事实上, 有两次当我和别人讨论时,我 说你知道状态机中真正重要的事情,他们对我说 那篇论文里没有关于状态机的内容,我不得不回去查看 论文以说服自己我没有发疯,论文中确实没有提到 状态机。我一直不太理解为什么这篇论文在计算机科学中被认为 如此重要,因为它提出的算法 并没有特别的兴趣,它具有历史意义,
HN 上的讨论
这篇文章本身不怎么样,但它简要提到了 Leslie Lamport 1978 年的论文《Time, Clocks, and the Ordering of Events in a Distributed System》。在 2016 年的一次采访中,Lamport 谈到了他撰写这篇论文的经历及其与狭义相对论的联系。那次采访中的这个短片 [0] 值得一看。[0] [VIDEO] — chatmasta, 2024-02
这不是巧合。粗略地说,向量时钟建立在 Lamport 时钟的概念之上。这并不是说一种时钟比另一种更好。它们之间的选择取决于手头的任务,并涉及一系列权衡。无论如何,被认为是当今分布式系统奠基人的 Leslie Lamport 在他 1978 年的论文《时间、时钟和分布式系统中事件的排序》(后来因此获得图灵奖)中引入了 Lamport 时钟的概念。根据 Lamport 的说法,那篇论文直接受到狭义相对论的启发。用他自己的话 [^1]:“[...] 狭义相对论,特别是闵可夫斯基在著名的 1908 年论文中发展的四维时空观。我意识到分布式系统中的问题与物理学中发生的事情非常相似 [...]”所以,我不知道这些算法是被重新发明还是(重新)发现,因为正如你正确指出的,它们恰好在我们宇宙中运行。[^1]: [VIDEO] — myk9001, 2023-07
即使对于时钟偏差非常低的地面应用,有一个概念来区分哪些事件可能受到先前事件的影响,哪些不可能,也是非常有帮助的。但你的物理类比完全正确。Lamport 本人说,他对狭义相对论的知识帮助他提出了这个概念。[VIDEO] — LAC-Tech, 2023-02
相关视频
- 与George Hotz一起越狱模拟 | SXSW 2019 · SXSW · 55:59
- DEF CON 23 - Chris Rock - 我会杀了你 · DEFCONConference · 31:28
- AT&T档案:波行为的相似性(特别版) · AT&T Tech Channel · 28:02
- Erlang和Elixir的灵魂 • Sasa Juric • GOTO 2019 · GOTO Conferences · 42:02
- Micro Men - 720p (2009) · gimpymoo · 1:24:12
- Jim Simons(完整版访谈)- Numberphile · Numberphile2 · 1:00:43
- 遥遥领先 | 1969 年的阿波罗制导计算机 · TNMoC · 1:21:22
- Steve Jobs 2005 年斯坦福大学毕业演讲 · JoshuaG · 14:34
- “用确定性模拟测试分布式系统” by Will Wilson · Strange Loop Conference · 40:20
- 机械计算机(全部部件)- 火控计算机的基本机构 · Excelsior10000 · 41:53
- Project Code Rush - Netscape / Mozilla 的开端纪录片 · The Documentary Network · 56:08
- Bret Victor:编程的未来 · Joey Reid · 32:55
- Alan Kay - 正常被认为有害 · powerfuloutlet · 1:07:26
- 培育语言,作者:Guy Steele · Bill Pugh · 53:31
- 软件设计哲学 | John Ousterhout | Talks at Google · Talks at Google · 1:01:40
- “Uncle” Bob Martin - “编程的未来” · Paul Stringer's Mobile Tech · 1:18:21