A Distributed Abstraction Algorithm for Online Predicate Detection
A Distributed Abstraction Algorithm for Online Predicate Detection
复制标题
DOI：
10.1109/srds.2013.19
复制
发表时间：
2013-04
期刊：
影响因子：
--
通讯作者：
Himanshu Chauhan;V. Garg;Aravind Natarajan;N. Mittal
中科院分区：
文献类型：
--
作者：
Himanshu Chauhan;V. Garg;Aravind Natarajan;N. Mittal
总体上，分析分布式计算是一个困难的问题，这是由于状态空间大小的组合爆炸与系统中的过程数量。通过抽象计算，可以避免不必要的状态探索。计算切片是针对给定谓词抽象分布式计算的一种方法。我们专注于常规谓词，这是一个涵盖许多常用谓词进行运行时验证的谓词。现有的计算切片算法是集中式的 - 单个过程负责以离线或在线方式计算切片。在本文中，我们介绍了第一个在线分布式算法，用于计算相对于常规谓词的分布式计算的切片。我们的算法在整个系统上分发了工作和存储要求，从而降低了每个过程的空间和计算复杂性。
Analyzing a distributed computation is a hard problem in general due to the combinatorial explosion in the size of the state-space with the number of processes in the system. By abstracting the computation, unnecessary state explorations can be avoided. Computation slicing is an approach for abstracting distributed computations with respect to a given predicate. We focus on regular predicates, a family of predicates that covers many commonly used predicates for runtime verification. The existing algorithms for computation slicing are centralized - a single process is responsible for computing the slice in either offline or online manner. In this paper, we present first distributed online algorithm for computing the slice of a distributed computation with respect to a regular predicate. Our algorithm distributes the work and storage requirements across the system, thus reducing the space and computation complexity per process.