Abstract
In this paper, we give an efficient algorithm to determine whether a locally stable predicate has become true in an underlying computation. Examples of locally stable predicates include termination and deadlock. Our algorithm does not require application messages to be modified to carry control information (e.g., vector timestamps), nor does it inhibit events (or actions) of the underlying computation. Once the predicate becomes true, the detection latency (or delay) of our algorithm is proportional to the time-complexity of computing a (possibly inconsistent) snapshot of the system. Moreover, only O(n) control messages are required to detect the predicate once it holds, where n is the number of processes.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chandy, K.M., Lamport, L.: Distributed Snapshots: Determining Global States of Distributed Systems. ACM Transactions on Computer Systems 3, 63–75 (1985)
Lai, T.H., Yang, T.H.: On Distributed Snapshots. Information Processing Letters (IPL) 25, 153–158 (1987)
Hélary, J.M., Jard, C., Plouzeau, N., Raynal, M.: Detection of Stable Properties in Distributed Applications. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 125–136 (1987)
Acharya, A., Badrinath, B.R.: Recording Distributed Snapshots Based on Causal Order of Message Delivery. Information Processing Letters (IPL) 44, 317–321 (1992)
Alagar, S., Venkatesan, S.: An Optimal Algorithm for Recording Snapshots using Casual Message Delivery. Information Processing Letters (IPL) 50, 311–316 (1994)
Ho, G.S., Ramamoorthy, C.V.: Protocols for Deadlock Detection in Distributed Database Systems. IEEE Transactions on Software Engineering 8, 554–557 (1982)
Misra, J.: Detecting Termination of Distributed Computations Using Markers. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 290–294 (1983)
Mattern, F.: Algorithms for Distributed Termination Detection. Distributed Computing (DC) 2, 161–175 (1987)
Dijkstra, E.W.: Shmuel Safra’s Version of Termination Detection. EWD Manuscript 998 (1987), Available at http://www.cs.utexas.edu/users/EWD
Mattern, F., Mehl, H., Schoone, A., Tel, G.: Global Virtual Time Approximation with Distributed Termination Detection Algorithms. Technical Report RUU-CS- 91-32, University of Utrecht, The Netherlands (1991)
Hélary, J.M., Raynal, M.: Towards the Construction of Distributed Detection Programs, with an Application to Distributed Termination. Distributed Computing (DC) 7, 137–147 (1994)
Brzezinski, J., Hélary, J.M., Raynal, M., Singhal, M.: Deadlock Models and a General Algorithm for Distributed Deadlock Detection. Journal of Parallel and Distributed Computing (JPDC) 31, 112–125 (1995)
Demirbas, M., Arora, A.: An Optimal Termination Detection Algorithm for Rings. Technical Report OSU-CISRC-2/00-TR05, The Ohio State University (2000)
Stupp, G.: Stateless Termination Detection. In: Proceedings of the 16th Symposium on Distributed Computing (DISC), Toulouse, France, pp. 163–172 (2002)
Khokhar, A.A., Hambrusch, S.E., Kocalar, E.: Termination Detection in Data- Driven Parallel Computations/Applications. Journal of Parallel and Distributed Computing, JPDC (2003)
Mahapatra, N.R., Dutt, S.: An Efficient Delay-Optimal Distributed Termination Detection Algorithm. Submitted to IEEE Transactions on Parallel and Distributed Systems (2003)
Marzullo, K., Sabel, L.: Efficient Detection of a Class of Stable Properties. Distributed Computing (DC) 8, 81–91 (1994)
Lamport, L.: Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM (CACM) 21, 558–565 (1978)
Tel, G.: Introduction to Distributed Algorithms, 2nd edn. Cambridge University Press, Cambridge (2000) (US Server)
Fromentin, E., Raynal, M.: Inevitable Global States: A Concept to Detect Unstable Properties of Distributed Computations in an Observer Independent Way. In: Proceedings of the 6th IEEE Symposium on Parallel and Distributed Processing (SPDP), pp. 242–248 (1994)
Mattern, F.: Virtual Time and Global States of Distributed Systems. In: Parallel and Distributed Algorithms: Proceedings of the Workshop on Distributed Algorithms (WDAG), pp. 215–226. Elsevier Science Publishers B. V, North-Holland (1989)
Fidge, C.: Logical Time in Distributed Computing Systems. IEEE Computer 24, 28–33 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Atreya, R., Mittal, N., Garg, V.K. (2004). Detecting Locally Stable Predicates Without Modifying Application Messages. In: Papatriantafilou, M., Hunel, P. (eds) Principles of Distributed Systems. OPODIS 2003. Lecture Notes in Computer Science, vol 3144. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27860-3_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-27860-3_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22667-3
Online ISBN: 978-3-540-27860-3
eBook Packages: Springer Book Archive