Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/61136
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.
URI: http://hdl.handle.net/10397/61136
ISSN: 0018-9340
EISSN: 1557-9956
DOI: 10.1109/TC.2015.2409839
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

3
Last Week
0
Last month
Citations as of Dec 9, 2017

WEB OF SCIENCETM
Citations

3
Last Week
0
Last month
Citations as of Dec 9, 2017

Page view(s)

33
Last Week
2
Last month
Checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric



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