An efficient implementation of vector clocks. (English) Zbl 0780.68050
Summary: The system of vector clocks is an essential tool for designing distributed algorithms and reasoning about them. We present an efficient implementation of vector clocks that reduces the size of timestamp related information to be transferred in a message. The implementation assumes FIFO message delivery and is resilient to changes in the topology of the distributed system.
MSC:
| 68W15 | Distributed algorithms |
Keywords:
distributed computing systems; logical time; vector time; causal ordering; vector clocks; distributed algorithms; efficient implementation; FIFO message deliveryReferences:
| [1] | Ahamad, M.; Hutto, P.; John, R., Implementing and programming causal distributed memory, Proc. 11th Internat. Conf. on Distributed Computing Systems, 274-281 (1991) |
| [2] | Birman, K.; Schiper, V.; Stephenson, P., Fast causal multicast, Computer Science Tech. Rept. TR-1105 (April 1990), Cornell University |
| [3] | Charron-Bost, B., Concerning the size of clocks, Inform. Process. Lett., 39, 1, 11-16 (1991) · Zbl 0735.68003 |
| [4] | Fidge, C. A., Partial order for parallel debugging, Proc. ACM SIGPLAN / SIGOPS Worshop on Parallel and Distributed Debugging, 183-194 (1988) |
| [5] | Fidge, C. A., Timestamps in message-passing systems that preserve partial ordering, Austral. Comput. Sci. Comm., 10, 56-66 (1988) |
| [6] | A.D. Kshemkalyani and M. Singhal, On characterization and correctness of distributed deadlock detection, OSU- CISRC-10/90-TR15 (under review for publication).; A.D. Kshemkalyani and M. Singhal, On characterization and correctness of distributed deadlock detection, OSU- CISRC-10/90-TR15 (under review for publication). |
| [7] | Lamport, L., Time, clocks, and the ordering of events in a distributed system, Comm. ACM, 21, 558-565 (1978) · Zbl 0378.68027 |
| [8] | Lloyd, S. K.; Kearns, P., Using tracing to direct our reasoning about distributed programs, Proc. 11th Internat. Conf. on Distributed Computing Systems, 552-559 (1991) |
| [9] | Mattern, F., Algorithms for distributed termination detection, Distributed Comput., 2, 161-175 (1987) |
| [10] | Mattern, F., Virtual time and global states of distributed systems, (Cosnard, M., Parallel and Distributed Algorithms (1989), North-Holland: North-Holland Amsterdam), 215-226 |
| [11] | Mattern, F., Verteilte Basisalgorithmen (1989), Springer: Springer Berlin, in German; ISBN 0-387-51835-5 · Zbl 0684.68009 |
| [12] | Meldal, S.; Sankar, S.; Vera, J., Exploiting locality in maintaining potential causality, Proc. ACM Symp. on Principles of Distributed Computing (1991), Stanford University, Tech. Rept. CSL-TR-91-466 · Zbl 1314.68383 |
| [13] | Parker, D. S.; Popek, G. J.; Rudisin, G.; Stoughton, A.; Walker, B. J.; Walton, E.; Chow, J. M.; Edwards, D.; Kiser, S.; Kline, C., Detection of mutual inconsistency in distributed systems, IEEE Trans. Software Engineering, 9, 240-247 (1983) |
| [14] | Schiper, A.; Eggli, J.; Sandoz, A., A new algorithm to implement causal ordering, (Proc. 3rd Internat. Workshop on Distributed Algorithms, 392 (1989), Springer: Springer Berlin), 219-232, Lecture Notes in Computer Science |
| [15] | Singhal, M., A heuristically-aided algorithm for mutual exclusion in distributed systems, IEEE Trans. Comput., 38, 5 (1989) |
| [16] | Strom, R.; Yemini, S., Optimistic recovery in distributed systems, ACM Trans. Comput. Systems, 3, 204-226 (1985) |
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.
