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

一个分布式系统,就是不同进程间消息传递的延时, 相比单进程的事件间隔, 大到不能被忽略的系统.

分布式系统中, 有时候没有办法区分两个事件的先后顺序. 因此"happened before"这种关系是一种偏序的关系.

本文讨论"happend before"这种关系, 同时给出一个分布式算法来扩展它, 构造所有事件的以一个一致的全序.

## The Partial Orderinig

"happend-before"关系的定义不包含物理时钟.

定义系统:
1. system由一组process组成
2. 每个process由一串顺序事件组成.

`->`(happend-before)定义:
1. 如果a和b是同一进程的事件, a先于b到, 则`a->b`.
2. 如果a是从进程1发送消息, b是从进程2接受该消息, 则`a->b`.
3. 如果`a->b`, `b->c`, 则`a->c`. 

如果两个事件a, b, 满足`a-/->b`, 且`b-/->a`, 那么就说这两事件并发.

`->`是个没有自反性的关系(irreflexive).

一种视角看`a->b`的关系, 就是a可能在因果上影响了b.


## Logical Clocks

逻辑时钟实际的作用是向系统中所有的事件event颁发一个数字作为时序.

可以看做一个函数`C_i(a)`, 输入是事件, 下标i是进程id, 输出是number.