On the minimal information to encode timestamps in distributed computations. (English) Zbl 1051.68037
Summary: Timestamping protocols are used to capture the causal order or the concurrency of events in asynchronous distributed computations. In this paper we give an answer to the open problem issued by R. Schwarz and F. Mattern [Distrib. Comput. 7, 149–174 (1994; Zbl 0813.68096)] about the minimum amount of information managed by protocols which represent causality in an isomorphic way. We point out that to encode each timestamp an amount of non-structured information (i.e., the number of bits) is necessary.
MSC:
| 68M14 | Distributed systems |
Citations:
Zbl 0813.68096References:
| [1] | Charron-Bost, B., Concerning the size of logical clocks in distributed systems, Inform. Process. Lett., 39, 11-16 (1991) · Zbl 0735.68003 |
| [2] | Fidge, C. J., Timestamps in message passing system that preserve the partial ordering, (Proc. of 11th Australian Computer Science Conf. (1988)), 55-66 |
| [3] | Lamport, L., Time, clocks and the ordering of events in a distributed system, Comm. ACM, 21, 7, 558-565 (1978) · Zbl 0378.68027 |
| [4] | Mattern, F., Virtual time and global states of distributed systems, Parallel Distrib. Algorithms, 215-226 (1988) |
| [5] | Raynal, M.; Singhal, M., Logical time: Capturing causality in distributed systems, IEEE Comput., 29, 2, 49-57 (1996) |
| [6] | 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 |
| [7] | Singhal, M.; Kshemkalyani, A., An efficient implementation of vector clocks, Inform. Process. Lett., 43, 47-52 (1992) · Zbl 0780.68050 |
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.
