Efficient online algorithm for identifying useless states in distributed systems. (English) Zbl 1231.68069
Summary: In a distributed system, detecting whether a given logical predicate is true on the global states is fundamental for testing and debugging the program. Detecting predicates by examining all global states is intractable due to the combinatorial nature of the problem. This work designs an efficient online algorithm that identifies the consistent and useless states each time a new state is reported. This paper formulates the optimality of detecting algorithms in terms of pseudo states, which are employed to represent unknown states to the monitor process. Based on this technique, memory space of the debugger can be minimized by removing the useless states without affecting the debugging results. While minimizing memory space, the proposed algorithm requires only \(O(p^{2} M)\) time in total, where \(p\) is the number of processes, and \(M\) is the number of reported states.
References:
| [1] | Chandy K.M., Lamport L.: Distributed snapshots: determining global states of distributed systems. ACM Trans. Comput. Syst. 3(1), 63–75 (1985) · doi:10.1145/214451.214456 |
| [2] | Chen L.B., Wu I.C.: An efficient distributed online algorithm to detect strong conjunctive predicates. IEEE Trans. Softw. Eng. 28(11), 1077–1084 (2002) · doi:10.1109/TSE.2002.1049405 |
| [3] | Chiou H.K., Korfhage W.: Enhancing distributed event predicate detection algorithms. IEEE Trans. Parallel Distrib. Syst. 7(7), 673–676 (1996) · doi:10.1109/71.508247 |
| [4] | Cooper, R., Marzullo, K.: Consistent detection of global predicates. Sigplan Notices, pp. 167–174 (1991) |
| [5] | Garg V.K., Waldecker B.: Detection of weak unstable predicates in distributed programs. IEEE Trans. Parallel Distrib. Syst. 5(3), 299–307 (1994) · doi:10.1109/71.277788 |
| [6] | Garg V.K., Waldecker B.: Detection of strong unstable predicates in distributed programs. IEEE Trans. Parallel Distrib. Syst. 7(12), 1323–1333 (1996) · doi:10.1109/71.553309 |
| [7] | Helary J.M., Mostefaoui A., Netzer R.H.B., Raynal M.: Communication-based prevention of useless checkpoints in distributed computations. Distrib. Comput. 13(1), 29–43 (2000) |
| [8] | Hurfin M., Mizuno M., Raynal M., Singhal M.: Efficient distributed detection of conjunctions of local predicates. IEEE Trans. Softw. Eng. 24(8), 664–677 (1998) · doi:10.1109/32.707701 |
| [9] | Kshemkalyani A.D.: The power of logical clock abstractions. Distrib. Comput. 17(2), 131–150 (2004) |
| [10] | Kshemkalyani A.D.: A fine-grained modality classification for global predicates. IEEE Trans. Parallel Distrib. Syst. 14(8), 807–816 (2003) · doi:10.1109/TPDS.2003.1225059 |
| [11] | Lamport L.: Time, clocks and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978) · Zbl 0378.68027 · doi:10.1145/359545.359563 |
| [12] | Mattern, F.: Virtual time and global states of distributed systems. In: Parallel and Distributed Algorithms: Proceedings of the International Workshop on Parallel and Distributed Algorithms, pp. 215–226. Elsevier, New York (1989) |
| [13] | Mittal N., Garg V.K.: Techniques and applications of computation slicing. Distrib. Comput. 17(3), 251–277 (2005) · Zbl 1264.68030 · doi:10.1007/s00446-004-0117-0 |
| [14] | Manivannan D., Netzer R.H.B., Singhal M.: Finding consistent global checkpoints in a distributed computation. IEEE Trans. Parallel Distrib. Syst. 8(6), 165–169 (1997) |
| [15] | Netzer H.B., Xu J.: Necessary and sufficient conditions for consistent global snapshots. IEEE Trans. Parallel Distrib. Syst. 6(2), 165–169 (1995) · doi:10.1109/71.342127 |
| [16] | Schwarz R., Mattern F.: Detecting causal relationships in distributed computations: In search of the holy grail. Distrib. Comput. 7(3), 149–174 (1994) · Zbl 0813.68096 · doi:10.1007/BF02277859 |
| [17] | Wang Y.M.: Consistent global checkpoints that contain a given set of local checkpoints. IEEE Trans. Comput. 46(4), 456–468 (1997) · doi:10.1109/12.588059 |
| [18] | Wang Y.M., Chung P.Y., Lin I.J., Fuchs W.K.: Checkpoint space reclamation for uncoordinated checkpointing in message-passing systems. IEEE Trans. Parallel Distrib. Syst. 6(5), 546–554 (1995) · doi:10.1109/71.382324 |
| [19] | Wang Y.M., Lowry A., Fuchs W.K.: Consistent global checkpoints based on direct dependency tracking. Inf. Process. Lett. 50(4), 223–230 (1994) · Zbl 0807.68012 · doi:10.1016/0020-0190(94)00038-7 |
| [20] | Wu I.C., Chen L.B.: On detection of bounded global predicates. Comput. J. 41(4), 231–237 (1998) · Zbl 0919.68015 · doi:10.1093/comjnl/41.4.231 |
| [21] | Yen L.H.: Precluding useless events for on-line global predicate detections. J. Parallel Distrib. Comput. 61(8), 1077–1095 (2001) · Zbl 0988.68014 · doi:10.1006/jpdc.2001.1740 |
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.
