Detection of summative global predicates

Abstract

In distributed programs, we usually keep some global predicates from being satisfied to make it easy to run the programs correctly. A common type of global predicates are: the total number of certain tokens in the whole distributed system is always the same or in specific ranges, In this paper; we call this summative predicates, classified into the following four: (1) at some global state of the system, N not equal K, (2) N < K (or N less than or equal to K), (3) N > K (or N greater than or equal to K), and (4) N = K, where N is the fetal number of tokens and ii is a constant. This paper investigates the methods of detecting various summative global predicates, The first class of summative predicates are trivial to detect by simply checking each message, For the second class of summative predicates, Groselj [6] and Garg [2] solved the problem by reducing the problem to a maximum network pou: problem. In this paper, we propose an elegant technique, called normalization, to allow the second and third classes of summative predicates to be solved by also reducing the problem to a maximum network pou: problem. For the fourth floss of summative! predicates, we prove that it is an NP-complete problem.