Detection of summative global predicates

L. B. Chen*, I-Chen Wu

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

3 Scopus citations

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≠K, (2) N<K (or N≤K), (3) N>K (or N≥K), and (4) N = K, where N is the total number of tokens and K 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 flow 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 flow problem. For the fourth class of summative predicates, we prove that it is an NP-complete problem.

Original languageEnglish
Pages466-473
Number of pages8
DOIs
StatePublished - 1 Dec 1997
EventProceedings of the 1997 International Conference on Parallel and Distributed Systems - Seoul, South Korea
Duration: 10 Dec 199713 Dec 1997

Conference

ConferenceProceedings of the 1997 International Conference on Parallel and Distributed Systems
CitySeoul, South Korea
Period10/12/9713/12/97

Fingerprint Dive into the research topics of 'Detection of summative global predicates'. Together they form a unique fingerprint.

Cite this