Concerning the size of logical clocks in distributed systems (Q1182109)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Concerning the size of logical clocks in distributed systems |
scientific article |
Statements
Concerning the size of logical clocks in distributed systems (English)
0 references
27 June 1992
0 references
\textit{C. Fidge} [Timestamps in message passing systems that preserve the partial ordering in Proc. 11th Australian Computer Science Conf., 55-66 (1988)] and \textit{F. Mattern} [Virtual time and global states of distributed systems in Parallel and Distributed Algorithms, Amsterdam: North-Holland, 215-226 (1988)] improve \textit{L. Lamport}'s [Commun. ACM 21, 558-565 (1978; Zbl 0378.68027)] logical time with a clock that entirely reflects the partial order defined by the causality relation. The events are timestamped by vectors of \(\mathbb{N}^ n\), where \(n\) is the number of processes. The use of such vectors may seem very heavy as soon as one is concerned with a distributed system on a large number of processes. We prove that vectors of this length are necessary to characterize causality, by constructing an appropriate distributed computation. Then we use classical theorems from the theory of partially ordered sets to give a mathematical interpretation of this result.
0 references
distributed computing
0 references
logical time
0 references
clock
0 references
causality
0 references