Please use this identifier to cite or link to this item:
Title: Predicate detection in asynchronous distributed systems : a probabilistic approach
Authors: Zhu, W
Cao, J 
Raynal, M
Keywords: Asynchronous distributed systems
Occurrence probability
Occurrence times
Predicate detection
Issue Date: 2016
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on computers, 2016, v. 65, no. 1, 7056433, p. 173-186 How to cite?
Journal: IEEE transactions on computers 
Abstract: In an asynchronous distributed system, a number of processes communicate with each other via message passing that has a finite but arbitrary long delay. There is no global clock in that system. Predicates, denoting the states of processes and their relations, are often used to specify the information of interest in such a system. Due to the lack of a global clock, the temporal relations between the states at different processes cannot be uniquely determined, but have multiple possible circumstances. Existing works of predicate detection are based on the definitely modality or the possibly modality, denoting that a predicate holds in all of the possible circumstances or in one of them, respectively. No information is provided about the probability that a predicate will hold, which hinders the taking of countermeasures for different situations. Moreover, the detection is based on single occurrence of a predicate, so the results are heavily affected by environmental noise and detection errors. In this paper, we propose a new approach to predicate detection to address these two issues. We generalize the definitely and possibly modalities to an occurrence probability to provide more detailed information, and further investigate how to detect multiple occurrences of a predicate. We propose a unified algorithm framework for detecting various types of predicates and demonstrate the use of it for three typical types of predicates, including simple predicates, simple sequences, and interval-constrained sequences. Theoretical proofs and simulation results show that our approach is effective and outperforms existing approaches.
ISSN: 0018-9340
EISSN: 1557-9956
DOI: 10.1109/TC.2015.2409839
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Aug 9, 2018


Last Week
Last month
Citations as of Aug 16, 2018

Page view(s)

Last Week
Last month
Citations as of Aug 12, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.