×

Eventually perfect predicate detection in crash-affected finite average response time systems. (English) Zbl 1191.68082

Summary: Monitoring and predicate detection is a fundamental challenge of evaluating whether or not a predicate has held on the state of a distributed system in an execution. We solve eventually perfect predicate detection in a failure-prone system assuming that only the average response time is finite. The solution is based on an eventually accurate failure detection sequencer (\(\diamond \Sigma \)) which we propose and implement in the finite average response time system. We prove that \(\diamond \Sigma \) can solve eventually perfect detection of predicates involving process operational status. This research contributes to identifying realistic detection semantics in a weak partially synchronous model. Our approach has a layered model with which applications have the flexibility to choose appropriate predicate detection algorithms with the possibility to solve different predicate modalities.

MSC:

68M14 Distributed systems
68M15 Reliability, testing and fault tolerance of networks and computer systems
68W15 Distributed algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1109/32.940566 · Zbl 05114172 · doi:10.1109/32.940566
[2] DOI: 10.1145/226643.226647 · Zbl 0885.68021 · doi:10.1145/226643.226647
[3] DOI: 10.1145/200994.201005 · doi:10.1145/200994.201005
[4] DOI: 10.1007/s004460050049 · doi:10.1007/s004460050049
[5] DOI: 10.1145/122759.122774 · doi:10.1145/122759.122774
[6] DOI: 10.1109/ICDCS.2005.57 · doi:10.1109/ICDCS.2005.57
[7] Fischer M.J., Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory pp 127– (1983)
[8] DOI: 10.1109/ICDSC.2001.918962 · doi:10.1109/ICDSC.2001.918962
[9] DOI: 10.1007/3-540-45438-1_7 · doi:10.1007/3-540-45438-1_7
[10] Gärtner F.C., Proceedings of the 16th International Symposium on Distributed Computing (DISC ’02) pp 280– (2002)
[11] R. Guerraoui, R. Olivera, and A. Schiper, Stubborn communication channels, Technical Report 98-278, Département d’Informatique, École Polytechnique Fédérale de Lausanne, 1998
[12] DOI: 10.1145/359545.359563 · Zbl 0378.68027 · doi:10.1145/359545.359563
[13] DOI: 10.1109/EMPDP.2002.994241 · doi:10.1109/EMPDP.2002.994241
[14] Sen A., Proceedings of the 16th International Parallel and Distributed Processing Symposium (IPDPS ’02) pp 116– (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.