Maximal Antichain Lattice Algorithms for Distributed Computations
Maximal Antichain Lattice Algorithms for Distributed Computations
复制标题
分布式计算的最大反链格算法
DOI：
10.1007/978-3-642-35668-1_17
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
V. Garg
中科院分区：
文献类型：
--
作者：
V. Garg
分布式计算的最大反链格通常比它的一致全局状态格小得多。我们发现，一类有用的谓词可以检测到格的最大反链，而不是格的一致削减获得显着（指数为许多情况下）的储蓄。然后，我们提出了新的在线和离线算法来构建和枚举的最大反链格。以前已知的算法由Nourine和Raynoud [NR 99，NR 02]来构造格需要O（n 2 m）时间，其中n是计算中的事件数，m是最大反链格的大小。Rampon和Jard [JRJ94]的算法需要O（（n + w2）wm）时间，其中w是计算的宽度。所有这些算法都假设在新事件到来之前，输入的是最大反链格。我们提出了一个新的在线增量算法，OLMA，计算新添加的元素的晶格，而不需要事先的晶格。由于格在计算的大小上可以是指数的，所以我们在空间复杂度上得到了显着的降低。OLMA算法需要O（mw 2 logw L）时间和O（w L w logn）空间，其中w L是最大反链格的宽度。较低的空间复杂度使我们的算法适用于分布式系统中的在线全局谓词检测。为了分析离线轨迹，我们还提出了新的枚举算法来遍历格。
The lattice of maximal antichains of a distributed computation is generally much smaller than its lattice of consistent global states. We show that a useful class of predicates can be detected on the lattice of maximal antichains instead of the lattice of consistent cuts obtaining significant (exponential for many cases) savings. We then propose new online and offline algorithms to construct and enumerate the lattice of maximal antichains. Previously known algorithm by Nourine and Raynoud [NR99, NR02] to construct the lattice takes O(n 2 m) time where n is the number of events in the computation, and m is the size of the lattice of maximal antichains. The algorithm by Jourdan, Rampon and Jard [JRJ94] takes O((n + w 2)wm) time where w is the width of the computation. All these algorithms assume as input the lattice of maximal antichains prior to the arrival of a new event. We present a new online incremental algorithm, OLMA, that computes the newly added elements to the lattice without requiring the prior lattice. Since the lattice may be exponential in the size of the computation, we get a significant reduction in the space complexity. The OLMA algorithm takes O(mw 2 logw L ) time and O(w L w logn) space where w L is the width of the lattice of maximal antichains. The lower space complexity makes our algorithm applicable for online global predicate detection in a distributed system. For the purposes of analyzing offline traces, we also propose new enumeration algorithms to traverse the lattice.