Concerning the size of logical clocks in distributed systems (Q1182109): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A decomposition theorem for partially ordered sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5598296 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Time, clocks, and the ordering of events in a distributed system / rank | |||
Normal rank |
Revision as of 14:47, 15 May 2024
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