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

Concepts

• Distributed system

  • A collection of distinct processes which are spatially separated, and which communicate with each other by exchanging messages

  • Each process contains a sequence of events

• Three important concepts

  • Time

  • Clock

  • Ordering of events

    • "Happen before": partial ordering of the events in the system, without using physical clocks

• Though: problem of failures is a difficult one

  • The entire concept of failure is only meaningful in the context of physical time

  • Without it, there is no way of distinguish a failed process from one which is just puasing between events

• The partial ordering

  • -->: "happen before" relation.

    • If a and b are events in the same process, and a comes before b, then a --> b

    • If a is the sending of a message by one process and b is the receipt of the same message by another process, then a --> b

    • If a --> b and b --> c then a --> c

  • Two distinct events a and b are said to be concurrent if and

  • Irreflexive partial ordering on the set of all events in the system

  • 

• Logical clocks

  • Clocks: a way to assign number to the event, where the number is thought of as the time at which the event occurred

  • Clock $C_i$ for each process $P_i$ is a function which assigns a number $C_i<a>$to any event $a$ in that process (logical clock)

  • $C<b>=C_j<b>$ if b is an event in process $P_j$

  • 

    • But the converse condition is not true!

  • 

  • 

• Total ordering of the events

  • Define relation => as follows

    • If a is an event in process $P_i$ and b is an event in process $P_j$, then a => b if and only if either

      • 

      • 

    • This relation is a way of completing the "happened before" partial ordering to a total ordering

    • Clock condition implies that if a-->b then a ==> b

  • This ordering depends upon the system of clock $C_i$, and is not unique

    • Different choice of clocks which satisfy the clock condition yields different relation =>

    • It is only the partial ordering --> which is uniquely determined by the system of events

  • Why do we need total ordering?

    • The reason for implementing a correct system of logical clock is to obtain such total ordering

    • 逻辑时钟设计的最终目的就是为了得到一种事件全局排序的机制

  • Scenarios

    • System composed with a fixed collection of processes which share a single resource

    • Only one process can use the resource at a time, so the processes must synchronize themselves to avoid conflict

    • Find an algorithm for granting the resource to a process which satisfies the following condition

      • A process which has been granted the resource must release it before it can be granted to another process

      • Different requests for the resource must be granted in the order in which they are made

      • If every process which is granted the resource eventually releases it, then every request is eventually granted

• Anomalous Behavior (cite)

  • Person issues a request A on a computer A, and then telephones a friend in another city to have him issue a request B on a different computer B. It is possible for request B to receive a lower timestamp and be ordered before request A.

  • This can happen because the system has no way of knowing that A actually preceded B, since that precedence information is based on messages external to the system.

  • Two possible ways

    • Explicit introduce into the system about necessary information about the ordering

      • I.e. friend could specify that B be given a timestamp latter than T_A

      • This gives users the responsibility to avoid anomalous behavior

    • Construct a system of clocks which satisfies (i.e. properly synchronized physical clocks)

      • 

      • Stronger than ordinary clock condition because --> is a stronger relation than ->

      • 

      • The discussion on the physical clock references the paper (the following materials are from the reference reading) --> need to understand and revisit this part

      • Goal: 通过运行一个时钟同步算法，保证时钟对于任何事件打上的时间戳都不产生前面的异常行为（anomalous behavior）。也就是说，对于任意两个有偏序关系的事件（或者说可能在因果性上产生影响的两个事件），我们的物理时钟要保证总是会为后一个事件打上一个更大的时间戳。要实现这个目标，我们面临的障碍主要来源于物理时钟的两种误差：

        • 时钟的运行速率跟真实时间的流逝速率可能有差异；

        • 任意两个时钟的运行速率有差异，它们的读数会漂移得越来越远。

      • Lamport在论文中提出的物理时钟同步算法 将这两种时钟误差考虑在内，不断地对各个进程本地的物理时钟进行微调，把误差控制在能够满足Strong Clock Condition的范围内。

      • 分别考虑进程内的事件和跨进程的事件：

        • 对于进程内发生的不同事件，必须保证后发生的事件比先发生的事件时间戳要大。这实际上是要求我们保证每个物理时钟实例的读数总是单调递增的。这是比较容易实现的，我们只需要在微调时钟读数的时候，只把读数调大而不把读数调小。

        • 对于发生在两个不同进程上的事件

          • 为了保证不出现异常行为，我们就要求，不管A向B传递信息这个过程发生的速度有多快（最快可以达到光速，但在实际系统中，由于网络延迟和缓存等原因会慢很多），请求B发生时的时钟读数都必须大于请求A发生时的时钟读数。

          • 这个要求可能没法被满足的原因在于两边的物理时钟可能有误差。

          • 因此，就需要在不同的物理时钟之间交换信息，并借助这些信息同步时钟读数。

            • Expect 可以把时钟之间的误差控制在一定范围内 （只要我们在时钟之间交换信息足够频繁）。这是两种机制的赛跑：

              • 一方面，A通过系统外的方式向B传递信息，只要这个过程足够快，他们就有可能“看到”时钟误差造成的时钟读数减退（也就是出现了异常行为）

              • 另一方面，物理时钟同步算法通过在时钟之间不断交换信息并按照一定规则调整时钟读数，将时钟误差控制在一定范围内。只要算法的各个参数设置得当，就能保证：即使A向B传递信息的速度达到物理极限——光速，他们也无法“看到”时钟读数的减退现象。于是，Strong Clock Condition就被满足了。