US 6,574,665 B1Grant

Hierarchical vector clock

Issue Date:2003-06-03

•14 Claims

•2 Drawing Sheets

Abstract

A hierarchial vector clock (HVC) providing a logical time system to a collection of distributed systems. HVC is not restricted to any fixed number of hierarchy levels and scals naturally when the number of levels increases. Unlike constant-size clocks, its storage and processing requirements grow gracefully at approximately a logarithmic rate with the number of distributed sites within the distributed system. HVC is well suited for modern, message-passing distributed systems which make use of highly hierarchical communication networks.

Metadata

Assignee

Lucent Technologies Inc.

Inventor

Denis Andreyevich Khotimsky

Application Information

Application Number:US 09/387,115

Filing Date:1999-08-31

Priority Date:1999-02-26

Art Unit:7

Classifications

IPC:

G06F 15173

Field of Search:

709247709237370400703 16703 17707201711121712200712222375354375240713 17702 76607 32714 47

Patent Drawings (2 sheets)

Description

[0002] This application claims the benefit of United States Provisional Application No. 60/121,750 filed Feb. 26, 1999 and incorporated herein by reference.

FIELD OF THE INVENTION

[0003] 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

[0004] 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

[0005] 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.

[0006] 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.

[0007] 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.

[0008] 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:

[0009] 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” (⋄);

[0010] the message tag domain, S;

[0011] 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;

[0012] 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:

[0013] e→f→C(e)<C(f) [1]

[0014] 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:

[0015] e→f⇄C(e)<C(f) [2]

[0016] and is isomorphic (or, equivalently, is said to characterize causality), if ∀e,f∈ in H:

[0017] e→f⇄C(e)<C(f);

[0018] e≡f⇄C(e)=C(f);

[0019] e∥f⇄C(e)⋄C(f).

DESCRIPTION OF THE PRIOR ART

Totally Ordered Process Event Sets

[0020] 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:

[0021] 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;

[0022] ii. if e denotes a message send event and f is a reception event of the same message by another process, then e→f,

[0023] iii. if e→f and f→g, then e→g.

Scalar Lamport Clock

[0024] 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.

[0025] 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

[0026] 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^thAustralian 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ⁿ, where n is the number of processes in the system. Each process P_imaintains a vector Vⁱ=(v₁ⁱv₂ⁱ. . . v_nⁱ), which contains one component per each parallel task.

[0027] Two vectors Vⁱand V^jare equal, if all their components are equal; Vⁱ<V^j, if and only if v_kⁱ≦v_k^j, for all k=1, . . . ,n, and there exist at least one k, such that v_kⁱ≦v_k^j. In all other cases, Vⁱand V^jare incomparable. For each event occurring at process P_i, the i-th component of the logical time vector Vⁱ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-local components of Vⁱare updated by taking the component-wise maximum of Vⁱand the sender's vector clock extracted from the message. Without loss of generality, the local component of a vector timestamp can be viewed as the sequential number of the event in the local event order. Then each non-local component corresponds to an index of the most recent event at process P_jwhich is known to process P_i.

[0028] The vector clock possesses a number of attractive properties. First,a logical time system based on a vector clock of size n is isomorphic. Besides, to determine causal relation between two distinct events e and f occurring, respectively, at process P_iand process P_j, which are not necessarily distinct, it is sufficient to compare only one component of their vector timestamps:

[0029] e→f⇄Vⁱ[i]≦V^j[i] [3]

[0030] However, B. Charron-Bost showed, in an article entitled “Concerning the size of logical clocks in distributed systems”, which appeared in Information Processing Letters, 39:11-16, 1991, that in order to maintain clock isomorphism, the size of the vector timestamp has to be at least equal to the number of processes in the system. Therefore, the storage and communication overhead, as well as the processing time, grow linearly with the system size n, making the cost of the vector clock in a large distributed system prohibitively high.

Isomorphic Variations of Vector Clock

[0031] A number of vector clock optimizations applicable in certain special cases have been proposed. The differential technique of M. Singhal and A. Kshemkalyani (See, e.g., M. Singhal and A. Kshemkalyani, “An efficient implementation of vector clocks”, Information Processing Letters 43(1):47-52, August 1992), reduces the communication overhead by transmitting only those vector components that have changed since the most recent transfer. The dependency method described by J. Fowler and W. Zwaenopoel, in an article entitled “Causal distributed breakpoints”, that appeared in Proc. 10th Intl. Conf. Distributed Computing Systems (ICDCS-10), Paris, France, May 28-Jun. 1, 1990. EEE, allows a process to store only the information related to the direct dependencies between processes and reduces the size of a message tag to a scalar value, at the expense of the substantial latency and overhead required to recursively recompute the causal precedence information off-line. Other proposed optimization can be found in an article entitled “Incremental transitive dependency tracking in distributed computations”, authored by C. Jard and G. V. Jourdan, that appeared in Parallel Processing Letters}, 6(3):427-435, September 1996. All these techniques described are restricted to the certain special cases and don't affect the impossibility result described in the art.

Matrix Clock

[0032] Another related approach which has been used to discard obsolete information in replicated databases is the matrix clock, as described by Wuu and Bernstein in an article entitled “Efficient solutions to the replicated log and dictionary problems”, that appeared in Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, pages 233-242, Vancouver, B. C., Canada, Aug. 27-29, 1984, and an article by Sarin and Lynch entitled “Discarding obsolete information in a replicated database system”, tse, SE-13(1):39-47, January 1987.

[0033] Both the event timestamps and the message tags are defined on the set of integer matrices Nⁿ×Nⁿ, where k-th component of the j-th row of the logical time matrix maintained by process P_icorresponds to the P_i's view of the most recent event belonging to the process P_kwhich is known to process P_j. The (i,i)-th component of the P_i's logical time matrix is incremented for each local event occurring at P_i, the other components are updated by taking the component-wise maximum of the local matrix and the message tag. The memory and communication overhead of the matrix clock prevents its usage to determine causality in large distributed systems.

Non-Isomorphic Approximations of Vector Clock

[0034] A class of logical time systems, referred to as Plausible clocks, sacrifice isomorphism to maintain simplicity of the timestamps and messages, are defined by the following properties:

[0035] e≡f⇄C(e)=C(f);

[0036] e→f⇄C(e)<C(f); [4]

[0037] e←f⇄C(e)>C(f).

[0038] They can be viewed as an approximation of the isomorphic vector clock which are able to detect concurrency between events in H with certain degree of accuracy. The plausible logical time systems form a partial hierarchy, any two of which can be combined to produce another plausible logical time system of higher accuracy than the original ones. A simple example of plausible clock is provided by Lamport clock with the added process identity to disambiguate between different events having the same scalar timestamp is plausible. Another examples of the constant size plausible clocks include the R-entry vector clock and the K-Lamport clock.

[0039] R-entry vector clock is a variant of the vector clock with added process identity where the event timestamps and the message tags belong to a vector space N^r, and the vector size r is fixed and independent of n, the number of processes in the system. Each component of the vector timestamp corresponds to the maximum sequential index of an event occurring at some subset of processes in the system, such that this event causally precedes the given local event. The simple mapping of a process identity into the vector component index is given by a modulo-r function. The vector timestamp comparison function can be modified accordingly, so that ∀e,f∈ H:

[0040] C(e)<C(f)→(e→f)ν(e∥f);

[0041] C(e)⋄C(f)→(e∥f).

[0042] K-Lamport clock is an extension of the Lamport clock with the logical time domain T=N^Kand the message tag domain G=N^K−1. The timestamp of each event is comprised of the process identity, the scalar Lamport timestamp, and a (K−1)-dimensional vector of maximum tags received by the process itself as well as its direct and indirect message suppliers. The process' Lamport clock and K−2 components of the maximum received tag vector are included with each message. The Lamport clock is maintained in the usual way, whereas on a message receipt event, the k-th component of the local logical time vector, k>1, is set to a maximum of its previous value and the value of (k−1) component of the message tag. Using all the components when comparing timestamps allow, in some cases, to detect concurrency between events whose scalar timestamps (or vector timestamps of smaller size) are consistent with the existence of causal ordering.

Partially Ordered Process Event Sets

Model

[0043] The model of distributed computation originally considered by Lamport was based on the assumption that all events occurring within the same process are sequentially ordered. This model is not applicable in a multithreaded process environment where the tasks are being created and terminated dynamically and executed in parallel, yet the data and control dependencies may exist that establish causal relation between events of different tasks. The straight-forward solution based which attempts to consider each thread as a process in the original model is quite limited, as in this case the size of the data structures to maintain the isomorphic logical time and the associated processing and communication overhead become unbounded.

[0044] For a process with partially ordered event sets, two types of event causality relations are defined: internal causality and message causality. Internal causality is induced between the events of the same process by the existing data and control dependencies which are assumed to be known to the process. Message causality exists between each pair of corresponding message send and message receive events. The causal precedence relation on the entire event set of the distributed system is the transitive closure of the union of the two.

Vector Clock Extensions

[0045] C. Fidge, in an article entitled “Logical time in distributed computing systems”, which appeared in Computer, Vol. 24(8), pp. 28-33, 1991, suggested a method to apply the vector time approach to parallel environment. Fidge extended the Lamport definition of the “happened-before” to include the causal ordering created by forking a task and terminating a task, and replaced the notion of a vector by a set-of-pairs concept, where each pair pertains to a parallel task and contains the task identifier and the counter value. This method requires that the number of task be bounded by a value known in advance and does not allow recursive task definition.

[0046] More recently, Audenaert, in an article entitled “Clock trees: Logical clocks for programs with nested parallelism”, that appeared in IEEE Transactions on Software Engineering, Vol. 23, pp. 646-658, October 1997, proposed a new timestamping method of clock trees which applies in a distributed system where processes exhibit nested parallelism. A nested-parallel execution can be recursively decomposed into unnested partially ordered sets of events. Each partially ordered segment of parallel tasks may:

[0047] i. entirely belong to the causal past of the given event, or

[0048] ii. entirely lay outside its causal past, or

[0049] iii. belong to the casual past only partially.

[0050] In the first case (i) the segment of parallel tasks is treated as a single event in the execution history of the respective process; a single component in the vector timestamp of the given event suffices to capture the causal ordering. This timestamp is referred to as a quotient vector. In case (iii) case, however, additional information is required. This information is provided by a remainder vector that contains one clock tree for each parallel task in the nested segment. This recursive definition gives rise to a tree structured clock where each node, or local component, contains the event's quotient vector and the event's remainder vector for the current level of decomposition.

[0051] The clock trees are effective for the special case of distributed computation. In the general case their size effectively reaches that of a flat vector clock (and even exceeds it due to the overhead pointer structures).

Bit Matrix Clock

[0052] Bit-matrix clock is an isomorphic logical time system for processes with partially ordered events sets. (See, e.g., Ahuja, Carlson, and Gahlot, “Passive-space and time view: Vector clocks for achieving higher performance, program correction, and distributed computing”, IEEE Transactions on Software Engineering, Vol. 19(9), pp. 845-855, September 1993.) For a distributed system containing n processes, the logical time domain T of bit-matrix clock is the set of all non-negative integer vectors of size n: T=N_n. However, unlike the regular vector clock, each component of the vector is interpreted as a bitmap, rather than an event counter: the k-th bit position of the j-th component of the clock structure maintained by process P_iis 1, if the k-th event of process P_jcausally precedes the current event of process P_i; the bitmap position is 0 otherwise. The length of j-th component grows linearly with the number of events occurring at process P_j.

[0053] All bitmap components are initialized to zero and are updated with each internal or message send event by taking the bit-wise inclusive-or operation over bit-matrix timestamps of all local events that causally precede the given event. It can be done using the process' knowledge of the internal data and control dependencies and the timestamps of the local events. Besides, the bit corresponding to the event itself in the local bitmap vector component is set to 1. Each transmitted message carries the entire timestamp of the corresponding send event. On message receive event, the timestamp is computed by taking the bit-wise inclusive-or operation over bit-matrix timestamps of all local events that causally precede the given event and the corresponding send event timestamp extracted from the message. The corresponding to the event itself is also set.

Modifications To The Bit Matrix Clock

[0054] Two alternative representations of the dependency information were proposed in an article by Prakash and Singhal entitled “Dependency sequences and hierarchical clocks: Efficient alternatives to vector clock for mobile computing systems”, that appeared in Wireless Networks, 41(2):349-360, 15 March 1997. The method of dependency sequences presents an alternative encoding of the bitmap vector components which allows to store and transmit the sets of dependency gaps expressed in terms of local event identity pairs, rather than the bitmap itself This method may or may not be advantageous depending on the bitmap pattern. Generally, any lossless data compression technique may be useful in this situation.

[0055] Another method, described by Gahlot and Singhal in an article entitled “Heirarchial Clocks”, that appeared as a Technical Report OSU-CISRC-93-TR19, Dept. of Comput. and Inf. Sci., Ohio State Univ., Columbus, Ohio., USA, May 1993, can be described as two-level hierarchical clock. In order to reduce the on-line communication and storage overhead, the method uses a timestamp which contains a global component analogous to a conventional vector clock, and a local component which is represented by a variable length bit-vector specifying the causal precedence within the process event set. Unfortunately, the definition of the causal precedence relation used in deriving the two-level hierarchical clock is not without problems, therefore continuing methods and approaches are requried.

SUMMARY OF THE INVENTION

[0056] I have developed a new logical time system, the Hierarchical Vector Clock (HVC), which can be used to capture casual precedence relation in the large distributed systems with dynamically varying number of processes. Hierarchical Vector Clock is a variable size clock; while approximating the isomorphic vector clock, it requires much smaller communication and storage overhead: for distributed system containing N^Kprocesses, its communication and storage requirements are of the order N×K.

[0057] Hierarchical Vector Clock is both hierarchical and scalable. It is not restricted to any fixed number of hierarchy levels and can be naturally extended by employing the nested data structures and recursive invocation of the algorithms. In the simplest single-layer case, HVC becomes a variation of an isomorphic vector clock. HVC is ideally suited for the modern message-passing distributed systems which use the underlying communication networks of highly hierarchical structure.

[0058] Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention are described in detail below with reference to the accompanying drawing.

BRIEF DESCRIPTION OF THE DRAWING

[0059] FIG. 1 shows an example of a hierarchical distributed system with L=3; and

[0060] FIG. 2 shows an example of distributed computation.

DETAILED DESCRIPTION OF THE INVENTION

[0061] With reference now to FIG. 1, consider an asynchronous message-passing distributed system 100 in which processes are hierarchically grouped into clusters. On each level of hierarchy (101, 102, 103), such a cluster represents a logical node which belongs to a corresponding peer group of nodes. Each peer group, in its turn, makes a logical node on the higher level of hierarchy. A process itself is a logical node of the lowest level.

[0062] Let L be the total number of hierarchy levels in a system and assume that for a non-hierarchical system, L=1. Let G_k(P_i) denote the peer group to which a logical node encompassing process P_ibelongs on the k-th level of hierarchy. Then the process can be completely identified by its hierarchical address:

[0063] Addr (P_i)=<g₁ⁱ: g₂ⁱ: g₃ⁱ: . . . :g_Lⁱ≦; [5]

[0064] where g₁ⁱ≡pⁱis the P_i's process id within G₁(P_i), its peer group of the lowest level, and g_k, k=2, . . . , L, is the group id of the k-level logical node, which encompasses P_i, within the corresponding peer group. As can be appreciated, FIG. 1 shows an example of a hierarchical distributed system with L=3.

[0065] Let Hdist(P_i,P_j) be the hierarchical distance between processes P_iand P_j, i.e., the lowest level of hierarchy on which these processes appear in the same peer group of logical nodes (but not in the same logical node). For example, in FIG. 1, Hdist(P₁,P₃)=1, Hdist(P₂,P₆)=2, Hdist(P₇,P₈)=3. By definition Hdist(P_i,P_i)=0.

[0066] HVC applies the vector clock recursively on each level of hierarchy. This requires consolidation of a vector timestamp pertaining to a peer group into a single norm value associated with the logical node.

[0067] The domain of the logical time maintained by process P_iis the set of non-negative integer vectors:

[0068] T=N^Di., [6]

[0069] where D_i=Σ_k=^L∥G_k(P_i)∥. Here, ∥G∥ denotes cardinality of set G. Note the size of the logical clock may vary from one process to another and is guaranteed to remain the same only for the processes of the same lowest level peer group. The clock value maintained by process P_ican be represented as:

[0070] Vⁱ=({overscore (v)}₁ⁱ{overscore (v)}₂ⁱ. . . {overscore (v)}_Lⁱ); [7]

[0071] where {overscore (v)}_kⁱεN^∥G^(P^)∥. The components {overscore (v)}₁ⁱ└pⁱ┘{overscore (v)}₁ⁱ└pⁱ┘ and {overscore (v)}_kⁱ└g_kⁱ┘, k=2, . . . , L, are referred to as local components, since they pertain to the logical nodes in which process P_iappears itself. All vector components of HVC value are initially set to zero. When an internal event occurs, the local component of the lowest level vector is incremented, and the updated value is used to timestamp the event:

[0072] {overscore (v)}₁ⁱ└pⁱ┘={overscore (v)}₁ⁱ└pⁱ┘+1; [8]

[0073] When a message is sent by process P_ito process P_j(the communicating parties are supposed to know addresses of each other), in addition to the timestamping procedure analogous to that for an internal event, the message tag s has to be formed. The size and contents of the tag depend upon the value, r=Hdist(P_i, P_j). If r=1, the tag is identical to the timestamp of the send message event:

[0074] s:={overscore (v)}₁ⁱ, {overscore (v)}₂ⁱ, . . . {overscore (v)}_Lⁱ. [9]

[0075] If, on the other hand, 1<r≦L, then

[0076] s:={tilde over (v)}_rⁱ, {overscore (v)}_r+1ⁱ, . . . {overscore (v)}_Lⁱ. [10]

[0077] Where {tilde over (v)}_rⁱis obtained from {overscore (v)}_rⁱby substituting the level r logical time component by the local component of level 1:

[0078] {tilde over (v)}_rⁱ└g_rⁱ┘{overscore (v)}₁ⁱ└pⁱ┘+1; [11]

[0079] Note that when r=1, the transformation (11) gives a consistent result as well. An important property of the message tag is that its size gets smaller as the distance between the sender and the receiver in the process hierarchy increases.

[0080] Upon receipt of a message from process P_icarrying the tag

[0081] s=(s₀s₁. . . s_m); [12]

[0082] where m=L−Hdist,(P_i,P_j), process P_jupdates its logical time value by computing the component-wise maximum between the corresponding vectors:

[0083] {overscore (v)}_k^ji:=max{{overscore (v)}_k^j, s_k−r}, ∀k=r, . . . L; [13]

[0084] In addition, the local component of the lowest level vector is updated:

[0085] {overscore (v)}_k^ji[pⁱ]:=max{{overscore (v)}₁^j, p^j, s₀[g_rⁱ]}, +1; [14]

[0086] and the new value of the P_j's logical time is used to stamp the receive event.

[0087] The logical time maintenance and message tag construction rules are illustrated in FIG. 2. Observe that local component of the lowest level vector is nothing else than Lamport clock which is transmitted in each message regardless the hierarchical distance between the sender and the receiver. The lowest level vector itself is similar to a vector clock, keeping the index of the most recent event which have occurred at a corresponding process within the same lowest level peer group and which became known to the given process through a message exchange that group. It differs from a conventional vector clock in that the event indices grow faster, since they are updated on each message receipt according to the Lamport's maximization rule, rather than by unit increments. Similarly, the higher level vector components keep the indices of the most recent events which occurred in a corresponding logical node and became known to the given process through a message exchange taking place entirely between the processes of the same peer group of nodes on the respective level of hierarchy.

Causal Precedence

[0088] Given a pair of events, e and f identified by their timestamps, V^eand V^f, and the respective process addresses, Addr(P_i) and Addr(P_j), we would like to establish, with some degree of accuracy, the existence of the causal ordering between these events. First, we use the Lamport component of the timestamps, L(e)={overscore (v)}₁^e[pⁱ] and L(e)={overscore (v)}₁^f[p^ji], to formulate a hypothesis about their causal ordering and then verify that hypothesis using the available information. Note that in the trivial case, Addr(P_i)=Addr(P_j), Lamport clock completely and reliably characterizes causality.

[0089] If Addr(P_i)≠Addr(P_j) and L(e)=L(f), we immediately conclude that events e and f are concurrent. Let L(e)<L(f). Then either events e and f are concurrent or e causally precedes f The core part of the procedure which tests the hypothesis that e→f is outlined below. Rejecting the hypothesis corresponds to establishing concurrency between e and f this decision is guaranteed to be accurate. If the hypothesis is confirmed, the conclusion e→f still may or may not be true.

[0090] 1. Compute r=Hdist(P_i,P_j).

[0091] 2. Do for all k in the range from L down to r, until decision is made:

[0092] if {overscore (v)}_k^f<{overscore (v)}_k^eor {overscore (v)}_k^f⋄{overscore (v)}_k^e,

[0093] then reject the hypothesis;

[0094] else if {overscore (v)}_k^e<{overscore (v)}_k^fand {overscore (v)}₁^e[pⁱ]≦{overscore (v)}_k^f[g_kⁱ]

[0095] then confirm the hypothesis;

[0096] else decrement k and iterate step 2.

[0097] If all of the heirarchy levels in the range have been checked and a decision has not been made, then reject the hypothesis.

[0098] Various additional modifications of this invention will occur to those skilled in the art. Nevertheless, all deviations from the specific teachings of this specification that basically rely upon the principles and their equivalents through which the art has been advanced are properly considered within the scope of the invention as described and claimed.

Claims

Certificate of Correction present

The claims shown below may not include correction changes. Use the corrected PDF for authoritative text.

What is claimed is:

1. A hierarchical vector clock method of detecting a causal precedence relation between events in an asynchronous distributed system, said system comprising:

a plurality of processes each of which is executing on a separate physical node and exchanging information with other processes by transmitting messages over a communications network connecting the nodes, said events including message receive events and message send events, said processes of the distributed system being hierarchically grouped on two or more hierarchy levels, wherein:

each hierarchy level comprises one or more peer groups;

each peer group comprises one or more logical nodes;

the processes are the logical nodes of the lowest hierarchy level; and

each logical node of an (i+1)-th hierarchy level represents a peer group of an i-th hierarchy level, where i≧1,

said method comprising:

maintaining logical time in each individual process, said logical time comprising a plurality of integer vectors, one said vector for each hierarchy level in the distributed system, each of said vectors having a size equal to the number of said logical nodes in said peer group of logical nodes on the respective hierarchy level.

2. The method of claim 1 wherein each component of each vector of said plurality of vectors maintained by said individual process is pre-initialized to an integer value, is non-decreasing with the evolution of the distributed system and

a) each component of the first vector of said plurality of vectors maintained by the individual processes is associated with each respective node of said peer group of logical nodes of the lowest hierarchy level;

b) exactly one of said components of said first vector corresponds to said process itself, said component being a local component of the lowest hierarchy level;

c) each component of second and higher vectors of said plurality of vectors is associated with each respective logical node of said peer group of logical nodes on the respective hierarchy level;

d) exactly one of said components of each vector is associated with a logical node to which said process belongs itself, said component being the local component of the respective hierarchy level.

3. The method of claim 2 wherein:

a) said local component of the lowest hierarchy level maintained by said individual process always exceeds the number of events in the longest chain of events causally preceding the current event of said individual process, said local component of the lowest hierarchy level being a Lamport clock of said individual process;

b) each non-local component of said first vector maintained by said individual process is equal to the largest value of the Lamport clock of respective other processes of said peer group of nodes of the lowest hierarchy level, said largest value corresponding to an event of said other processes, said event causally preceding the current event of said individual process;

c) said local component of said second and higher vectors of said plurality of vectors maintained by said individual process is equal to the largest value of the Lamport clock of other processes of the same logical node on the respective hierarchy level, said largest value corresponding to an event of one of said other processes, said event causally preceding the current event of said individual process; and

d) each non-local component of said second and higher vectors of said plurality of vectors maintained by said individual process is equal to the largest value of the Lamport clock of a process belonging to another respective logical node of said peer group of logical nodes on the respective hierarchy level, said largest value corresponding to an event of said process of said respective other logical node, said event causally preceding the current event of said individual process.

4. The method according to claim 3 wherein each message sent by a first process to a second process of the distributed system contains a portion of the plurality of vectors maintained by the first process, said portion being restricted to those vectors of said plurality which correspond to the hierarchy levels on which the first process and the second process belong to the same peer group of logical nodes, the local component of the lowest sent vector being substituted by the Lamport clock of the first process.

5. The method according to claim 3 wherein

a) on occurrence of a local event of message send event at an individual process, the Lamport clock of the individual process is incremented by a positive integer value;

b) on receipt of a message from a first process occurring at a second process:

i) the Lamport clock value of the second process is set to the maximum of the previous Lamport clock value and the local component of the lowest sent vector of said message, said maximized Lamport clock value being incremented by a positive integer value;

ii) the vectors of theological time value maintained by said second process are updated by taking the component-wise maximum between the corresponding previous values and the values received in said message on the respective hierarchy levels.

6. The method according to claim 3 wherein each component of the plurality of vectors is pre-initialized to zero.

7. The method according to claim 5 wherein the Lamport clock of said individual process on occurrence of a local event or of a message send event is incremented by one.

8. The method according to claim 5 wherein the maximized Lamport clock of said second process on occurrence of a message receive event is incremented by one.

9. A method of detecting causal precedence in an asynchronous distributed system, comprising:

(A) organizing processes in the system into two or more hierarchy levels;

(B) for each process in the system, maintaining logical time using a set of two or more integer vectors, wherein:

each hierarchy level comprises one or more peer groups;

each peer group comprises one or more logical nodes;

the processes are the logical nodes of the lowest hierarchy level;

each logical node of an (i+1)-th hierarchy level represents a peer group of an i-th hierarchy level, where i>1;

for each process, the number of vectors in the set is equal to the number of hierarchy levels in the system and each vector in the set corresponds to a different hierarchy level; and

for each vector, the number of components in the vector is equal to the number of nodes in the corresponding peer group of the corresponding hierarchy level and each component of the vector corresponds to a different node of the peer group.

10. The invention of claim 9, wherein a number of processes in the system varies dynamically.

11. The invention of claim 9, wherein, for at least two processes in the system, vectors corresponding to the same hierarchy level have different numbers of components.

12. The invention of claim 9, further comprising:

(D) updating logical time corresponding to the second process using the time tag.

13. The invention of claim 12, wherein sending the message comprises:

(C1) determining hierarchical distance between the first and second processes; and

(C2) generating the time tag based on the hierarchical distance and logical time corresponding to the first process.

14. The invention of claim 12, wherein updating the logical time comprises, for each vector component corresponding to the second process, generating a new value for the component by selecting a maximum value from (i) a current value of the component and (ii) a value in the time tag corresponding to the component.

Patent Citations (10)

Patent	Date	Inventor	Cited By
US5138615(A)	1992-08-01	Lamport et al.	Examiner
US5524212(A)	1996-06-01	Somani et al.	Examiner
US5581753(A)	1996-12-01	Terry et al.	Examiner
US5627984(A)	1997-05-01	Gupta et al.	Examiner
US5745700(A)	1998-04-01	Caci	Examiner
US5768500(A)	1998-06-01	Agrawal et al.	Examiner
US5805874(A)	1998-09-01	Gallup et al.	Examiner
US5905766(A)	1999-05-01	Nguyen	Examiner
US6031987(A)	2000-02-01	Damani et al.	Examiner
US6341262(B1)	2002-01-01	Damani et al.	Examiner

Non-Patent Literature (21)

Plakal et al, Lamport Clocks: Verifying a Directory Cache-Coherence PRotocol, IEEE 6-7, 1998.Applicant
Meng, Optimistic Mechanism, www.cs.panam.edu/˜meng/Course/CS6337/Note/master/node22.html.Applicant
Lamport Clocks: Verifying a Directory Cache-Coherent Protocol. 1998.Applicant
“ATM-Forum Private Network-Network Interface Specification Version 1.0”, ATM Forum, Mar. 1966.Applicant
L. Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System”, Communications of the ACM, vol. 21, No. 7, Jul. 1978, pp 558-564.Applicant
D. Haban et al, “Global Events and Global Breakpoints in Distributed Systems”, Proceedings of the Twenty-First Annual Hawaii International Conference on System Sciences, Jan. 1988, pp 166-175.Applicant
F. Mattern, “Virtual Time and Global States of Distributed Systems”, Parallel And Distributed Aglorithms, M. Cosnard et al. (editors), Elsevier Science Publishers B. V. (North Holland), 1988, pp 215-226.Applicant
C. J. Fidge, “Timestamps in Message-Passing Systems That Preserve the Partial Ordering”, Proc. 11thAustralian Comp. Sci. Conference, 1988, pp. 56-66.Applicant
M. Raynal, “About Logical Clocks For Distributed Systems”, ACM Operating Systems Review, vol. 26, No. 1, Association for Computing Machinery, 1992, pp 41-48.Applicant
F. J. Torres-Rojas et al., “Plausible Clocks: Constant Size Logical Clocks For Distributed Systems”, Distributed Algorithms, 10th International Workshop, vol. 1151 of Lecture Notes In Computer Science, Babaoglu and Marzullo, editors, Bologna, Italy, Oct. 9-11, 1996, Springer Verlag, pp 71-88.Applicant
B. Charron-Bost, “Concerning The Size of Logical Clocks In Distributed Systems”, Information Processing Letters, vol. 39, 1991, pp 11-16.Applicant
M. Singhal et al, “An Efficient Implementation of Vector Clocks”, Information Processing Letters, vol. 43, No. 1, pp 47-51.Applicant
J. Fowler et al, “Causal Distributed Breakpoints”, Proc. 10th Intl. Conference Distributed Computing Systems (ICDCS-10), Paris, France, May 28-Jun. 1, 1990, pp 124-141.Applicant
C. Jard et al, “Incremental Transitive Dependency Tracking In Distributed Computations”, Parallel Processing Letters, vol. 6, No. 3, (1996), pp 427-435.Applicant
S. K. Sarin et al, “Discarding Obsolete Information in a Replicated Database System”, IEEE Transactions on Software Engineering, vol. SE-13, No. 1, Jan. 1987, pps 39-47.Applicant
C. Fidge, “Logical Time in Distributed Computing Systems”, Computer, Aug. 1991, pps 28-29.Applicant
K. Audenaert, “Clock Trees: Logical Clocks for Programs with Nested Parallelism”, IEEE Transactions on Software Engineering, vol. 23, No. 10, Oct. 1997, pps 646-658.Applicant
M. Ahuja et al, “Passive-space and Time View: Vector Clocks for Achieving Higher Performance, Program Correction and Distributed Computing”, IEEE Transactions on Software Engineering, vol. 19, No. 9, Sep. 1993, pps 845-855.Applicant
R. Prakah et al, “Dependency Sequences and Hierarchical Clocks: Efficient Alternatives to Vector Clocks For Mobile Computing Systems”, Wireless Networks, No. 3 (1997) pps 349-360.Applicant
A. Gahlot et al, “Hierarchical Clocks”, Technical Report OSU-CISRC-93-TR19, Dept. of Comput. and Inf. Sci., Ohio State Univ., Columbus, OH, USA, May 1993.Applicant
Wuu et al, “Efficient Solutions to the Replicated Log and Dictionary Problems”, Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, Vancouver, B.C., Canada, Aug. 27-29, 1984, pps 233-242.Applicant

Abstract