کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
426772 686267 2014 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Modeling, analyzing and slicing periodic distributed computations
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Modeling, analyzing and slicing periodic distributed computations
چکیده انگلیسی

The earlier work on predicate detection has assumed that the given computation is finite. Detecting violation of a liveness predicate requires that the predicate be evaluated on an infinite computation. In this work, we develop the theory and associated algorithms for predicate detection in infinite runs. In practice, an infinite run can be determined in finite time if it consists of a recurrent behavior with some finite prefix. Therefore, our study is restricted to such runs. We introduce the concept of d-diagram, which is a finite representation of infinite directed graphs. Given a d-diagram that represents an infinite distributed computation, we solve the problem of determining if a global predicate ever became true in the computation. The crucial aspect of this problem is the stopping rule that tells us when to conclude that the predicate can never become true in future. We also provide an algorithm to provide vector timestamps to events in the computation for determining the dependency relationship between any two events in the infinite run. Finally, we give an algorithm to compute a slice of a d-diagram which concisely captures all the consistent global states of the computation satisfying the given predicate.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 234, February 2014, Pages 26–43
نویسندگان
, , ,