Hierarchical vector clock

Details Hierarchical vector clock Hierarchical vector clock

1999-08-31

2003-06-03

Powell, Mark (Department: 2142)

Electrical computers and digital processing systems: multicomput

Computer network managing

Computer network monitoring

C703S017000

Reexamination Certificate

active

06574665

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to the field of distributed systems and in particular, to the application of logical time for detecting causality in a system containing a large number of distributed sites that don't share global memory and exchange information by passing messages over a communications network.
BACKGROUND OF THE INVENTION
Modern data networks possess a multilevel hierarchical structure (See, e.g.,“ATM-Forum Private Network-Network Interface Specification Version 1.0”, ATM Forum, March 1996), where certain sets of physical or logical nodes are grouped together according to physical, geographical, and/or administrative considerations. A distributed application running on such a network may involve thousands of sites belonging to different logical nodes with transport channels between them extending through multiple domain boundaries and crossing multiple hierarchical levels. Knowledge of causality between the events in such a system is essential for analyzing the system behavior and ensuring the correct operation through solving various problems related to mutual exclusion, consistency maintenance, fault tolerance and recovery. Unfortunately however, synchronous methods of causality tracking may be unavailable due to the absence of global clock and unpredictable communication delays, whereas straightforward logging of the local and remote events and exchanging logs along with messages is impractical due to a system's size and lifespan. In these circumstances, using logical time is a technique which allows efficient encoding of information contained in an event log and causality tracking while keeping the communication overhead low.
BASIC NOTIONS AND PROPERTIES
The notion of logical time, based on the concept of one event happening before another in a distributed system, was described by L. Lamport in an early paper entitled “Time, clocks, and the orderings of events in a distributed system”, which appeared in Communications of ACM, Vol. 21, pp. 558-564, 1978 and which subsequently attracted great amount of attention. (See, for example, Haban and Weigel, “Global events and global breakpoints in distributed systems”, Proceedings of the Twenty-First Annual Hawaii International Conference on System Sciences, pp. 166-175, January 1988; F. Mattern, “Virtual time and global states of distributed systems”, M. Cosnard et. al., editors, Proceedings of the International Workshop on Parallel and Distributed Algorithms, pp. 215-226, Amsterdam, 1989. Elsevier Science Publishers; C. J. Fidge, “Timestamps in message-passing systems that preserve the partial ordering”, Proc. 11th Australian Comp. Sci. Conf., pp. 56-66, 1988; M. Raynal, “About logical clocks for distributed systems”, “ACM Operating Systems Review”, vol. 26. Association for Computing Machinery, 1992; J. Torres-Rojas and Mustaque Ahamad, “Plausible clocks: Constant size logical clocks for distributed systems”, Babaoglu and Marzullo, editors, “Distributed Algorithms, 10th International Workshop”, vol. 1151 of “Lecture Notes in Computer Science”, pp. 71-88, Bologna, Italy, 9-11~October 1996. Springer Verlag.
In a distributed system, where no global shared memory is available and messages are exchanged over a communication network, event e is said to causally precede event f(e→f), if e can potentially affect f, in other words, by the epoch event f occurs, the process hosting event f has already received the information on the occurrence of event e.
Two distinct events e and f in H for which neither e→f of nor f→e holds are called concurrent (e∥f). Relation →is an order relation on the event set H of the distributed system, but it does not introduce a total order. Relation ∥ is not transitive.
Logical time provides a means to encode the causality information contained in the partial order (H, →) by assigning timestamps to all events, so that comparing two event timestamps allows one to draw a conclusion about the causal ordering of these events. Formally, a logical time system contains:
the logical time domain T with a comparison function f: T×T→R, where R is a set of four outcomes, “less than” (<), “greater than” (>), equal to” (=), and “incomparable” (⋄);
the message tag domain, S;
the set of rules which allow, for each send message event f, to form a message tag s(f)∈S to be transmitted along with the message;
a set of rules which allow the assignment of a timestamp C∈T to each event in the system's event set H, such that for any two events e, f∈H, the following condition holds:
e→f→C
(
e
)<
C
(
f
)  [1]
This monotonicity condition [1] is referred to as clock condition or weak clock consistency. A logical time system is strongly consistent if the converse of equation [1] holds, namely:
e→f⇄C
(
e
)<
C
(
f
)  [2]
and is isomorphic (or, equivalently, is said to characterize causality), if ∀e,f∈ in H:
e→f⇄C
(
e
)<
C
(
f
);
e≡f⇄C
(
e
)=
C
(
f
);
e∥f⇄C
(
e
)⋄
C
(
f
).
DESCRIPTION OF THE PRIOR ART
Totally Ordered Process Event Sets
Causal precedence or “happened-before” relation for a system with totally ordered process event sets was defined by Lamport for a system with totally ordered as the smallest relation on the set H of events in the system, such that:
i. if events e and f belong to the same process and e precedes f in the event sequence of that process, then e→f;
ii. if e denotes a message send event and f is a reception event of the same message by another process, then e→f,
iii. if e→f and f→g, then e→g.
Scalar Lamport Clock
Lamport defined a logical time system, commonly known as Lamport clock, which used the set of non-negative integers as the logical time domain, T=N. Each process maintains its logical time, which is initialized to zero and is incremented by 1 (or any positive value) when an internal event or message sent event occurs. The event is stamped with the value of the incremented logical time.
More specifically, the timestamp of a send message event is transmitted with the message (G=T). The timestamp of each message receive event is obtained by incrementing the maximum of the process' logical time value and the sender's timestamp extracted from the message. Thus the value of the process' logical time is always larger than the maximum message tag received so far, therefore, it could be shown that Lamport clock is weakly consistent. However, since non-negative integers form a totally ordered set, the Lamport clock does not allow one to capture concurrency.
Vector Clock
To overcome this problem, a concept of vector clock was later proposed by a number researches, most notably C. Fidge in an article entitled “Timestamps in message-passing systems that preserve partial ordering”, that appeared in
Proc
. 11
th
Australian Comp. Sci. Conf
., pp 55-66 in 1988; and an article by F. Mattern entitled “Virtual time and global states of distributed systems”, in Proceedings of the International Workshop on Parallel and Distributed Algorithms, M. Cosnard et. al. editors, pp. 215-226, Amsterdam, 1989, Elsevier Science Publishers. Logical time domain is an integer vector space T=N
n
, where n is the number of processes in the system. Each process P
i
maintains a vector V
i
=(v
1
i
v
2
i
. . . v
n
i
), which contains one component per each parallel task.
Two vectors V
i
and V
j
are equal, if all their components are equal; V
i
<V
j
, if and only if v
k
i
≦v
k
j
, for all k=1, . . . ,n, and there exist at least one k, such that v
k
i
≦v
k
j
. In all other cases, V
i
and V
j
are incomparable. For each event occurring at process P
i
, the i-th component of the logical time vector V
i
is incremented. For each send message event, the entire vector with the incremented local component is transmitted along with the message. When a message is received by P
i
, the non-l

Affiliated with

Also associated with

Rating

Hierarchical vector clock does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hierarchical vector clock, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical vector clock will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3127676