一个分布式系统,就是不同进程间消息传递的延时, 相比单进程的事件间隔, 大到不能被忽略的系统.
分布式系统中, 有时候没有办法区分两个事件的先后顺序. 因此”happened before”这种关系是一种偏序的关系.
本文讨论”happend before”这种关系, 同时给出一个分布式算法来扩展它, 构造所有事件的以一个一致的全序.
“happend-before”关系的定义不包含物理时钟.
定义系统:
system由一组process组成
每个process由一串顺序事件组成.
->(happend-before)定义:
如果a和b是同一进程的事件, a先于b到, 则a->b.
如果a是从进程1发送消息, b是从进程2接受该消息, 则a->b.
如果a->b, b->c, 则a->c.
如果两个事件a, b, 满足a-/->b, 且b-/->a, 那么就说这两事件并发.
->是个没有自反性的关系(irreflexive).
一种视角看a->b的关系, 就是a可能在因果上影响了b.
逻辑时钟实际的作用是向系统中所有的事件event颁发一个数字作为时序.
可以看做一个函数C_i(a), 输入是事件, 下标i是进程id, 输出是number.