九乡新闻网赵长军武术学院招生:推荐一篇文章<> - 刘杨 - 博客园
来源：百度文库 编辑：九乡新闻网 时间：2024/04/29 16:21:16
推荐一篇文章<>
简述:分布式系统包含一堆进程(processes)，进程间通过交换消息(message)彼此通讯。在分布式系统中，有时无法确定两个事件(event)的先后次序，所以先发生（happended before）关系在系统中只能是偏序（partialordering）。分布式系统中的问题很多源于人们尚未意识到这点及其涵义。
如前所述，假定系统由进程组成；而进程包含一个事件序列。即：若a先于b发生，则a在序列中比b靠前。因此在单一进程中的事件，其“先发生”是全序(total ordering)关系。假定进程收发消息也是事件，则可以用符号”->”指代”先发生”关系如下:
定义:
(1) 若a和b是同一进程中的事件,a比b先发生,则a->b;
(2) 若进程一发送一消息为事件a，进程二接收此消息为事件b，则a->b;
(3) 若a->b 和 b->c 则 a->c;
两事件a与b, 若a->b 与 b->a皆不成立, 则说二者同时发生 (concurrent)。
假定a->a不成立, 即”先发生”关系是非自反的(irreflexive).
上面图1表现时空关系, 横向是空间,纵向为事件, 先发生事件标记在下,波浪线为消息。例如如图我们有:p1->r4；而p3和q3则为同时关系。若您熟悉狭义相对论的时空表示，则看这幅图也不会觉得陌生。相对论中，事件的序（ordering）由能发送的消息定义（message that could be sent），而在此处，我们只考虑实际发送的消息（message that aresent）。
逻辑时钟：
现在引入逻辑时钟：为进程Pi定义时钟Ci, 它为进程中的每个事件a都赋予一个数字Ci[a].
对任意事件a和b: 若a->b 则C[a] < C[b]
注意反向未必成立.
易见:
C1. 若a和b是同一进程Pi的两个事件,且a先于b发生,则Ci[a] < Ci[b].
C2. 若Pi发送一消息为事件a, Pj接收同一消息为事件b, 则Ci[a] < Cj[b].
(未完待续)