A Distributed Abstraction Algorithm for Online Predicate Detection

被引：22

作者：

Chauhan, Himanshu ^{[1
]}

Garg, Vijay K. ^{[1
]}

Natarajan, Aravind ^{[2
]}

Mittal, Neeraj ^{[2
]}

机构：

[1] Univ Texas Austin, Dept Elect & Comp Engn, Austin, TX 78712 USA

[2] Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75083 USA

来源：

2013 IEEE 32ND INTERNATIONAL SYMPOSIUM ON RELIABLE DISTRIBUTED SYSTEMS (SRDS 2013) | 2013年

关键词：

D O I：

10.1109/SRDS.2013.19

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：101 / 110

页数：10

共 34 条

[1] Techniques to tackle state explosion in global predicate detection [J].

Alagar, S ;

Venkatesan, S .

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 2001, 27 (08) :704-714

[2]

[Anonymous], 2001, Model checking

[3]

Bauer A, 2016, FORM METHOD SYST DES, V48, P46, DOI [10.1007/s10703-016-0253-8, 10.1007/978-3-642-32759-9_10]

[4] DISTRIBUTED SNAPSHOTS - DETERMINING GLOBAL STATES OF DISTRIBUTED SYSTEMS [J].

CHANDY, KM ;

LAMPORT, L .

ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1985, 3 (01) :63-75

[5]

Chauhan H., 2013, ABS13044326 CORR

[6]

Chen F, 2007, LECT NOTES COMPUT SC, V4590, P240

[7]

Chen F, 2008, ICSE'08 PROCEEDINGS OF THE THIRTIETH INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, P221, DOI 10.1145/1368088.1368119

[8]

Cooper R., 1991, SIGPLAN Notices, V26, P167, DOI 10.1145/127695.122774

[9]

Darling D, 2006, LECT NOTES COMPUT SC, V3974, P161

[10]

Davey B.A., 1990, Introduction to Lattices and Order

← 1 2 3 4 →