B.同因果原子广播的比较
主次序原子广播设计成保持了因果次序特性,并瘾式地在增量状态更新创建时产生。在这一章节,我们将比较因果原子广播和主次序原子广播,并将论证,这两者是无法比较的。
因果次序的定义,是基于事件的前序(precedence, or happens before)关系。对于广播协议,事件分两种,要么是广播事件,要么是采用事件。我们采用<v, z> <c <v’, z’>,来表示abcast(<v, z>)先于abcast(<v’,z’>)发生。对于原子广播而言,因果次序基本定义为:
定义III.1. 因果次序:
如果<v, z> <c <v’, z’>,并且有进程p采用了<v’, z’>,那么该进程必定采用了<v,z>,并且先于<v’, z’>采用了<v, z>。
然而主次序原子广播并不满足因果次序特性。图三给出了一个例子。图中有两个事务<v, z>和<v’’, z’’>是因果关系,满足epoch(z) < epoch(z’) < epoch(z’’),但是事务<v,z>并没有被采用。简化起见,我们仅用事件来代表两个进程:
主次序原子广播下采用的顺序以主因果次序关系<po来表示,它比因果次序关系<c更弱。事实上,不同主进程发送的事务,没有必要必须因果关联,即使它们是被同一个进程发送,也是如此。我们说,一个事件ε以主次序先于ε’,或表示为ε->poε’,当且仅当以下条件之一成立:
1) 事件ε和ε’属于同一个进程,ε先于ε’发生,且以下条件之一成立:a). ε≠abcast(<v, z>)且ε’≠ abcast(<v’, z’>),或者b).epoch(z) = epoch(z’);
2) ε= abcast(<v, z>)并且ε’=abdeliver(<v’, z’>);
3) 存在事件ε’’,使得ε->poε’’且ε’’->poε’。
主因果次序关系<po的定义基于主次序先序关系(PO-precedence)。在因果关系定义中,我们用符号<po来替换<c 的,以此来表明主次序因果次序(PO causal order)。
主次序原子广播同样实现了另一个重要的特性,严格因果性(strict causality),即如果某个进程采用<v, z>和<v’, z’>,那么要么<v, z><po<v’, z’>,要么<v’, z’><po<v, z>。严格因果性是需要的,因为事务是基于增量更新方式广播,因此事务必须以产生它们时的相同状态,才能对该进行状态更新。于是这就是产生了因果关系更新链。然而,因果次序可以通过基于事务方式,而非因果关联进行发送。
图四展示了一个满足因果次序(也满足主次序因果次序 PO causal oder)的次序图,但它不满足严格因果性,因为<v, z>和<v’, z’>,即使它们没有因果关系,但都可以被采用。这表明严格因果性和主次序因果次序这两个原语,任何一个不比另一个更强(注:两者强弱无法比较)。