next up previous
Next: Checkpointing and Rollback-Recovery Up: Protocol Description Previous: Dependency Tracking

Causal Logging


Now, we have to slightly modify the write notice structure so that the happened-before-1 graph shown in Figure 3 can be reflected in the write notices. Figure 4.(a) represents the write notice structure supported by the existing LRC memory model for the computation shown in Figure 3, which consists of an array of N pointers, where N is the number of processes in the system. Each pointer indicates the list of the interval records created by each process, and each interval record contains the identifier of the corresponding process and the vector clock of the interval and a list of write notices for the write operations happened at the interval. The interval is created only at the release time after a write operation. As shown in the figure, since the intervals are arranged in the descending order of the vector clock, the structure naturally supports the directed edges within a process in the happened-before-1 graph.


  
Figure 4: The Revised Write Notice Structure
[IMAGE ]


To represent the edges between the distinct processes, we use a pair of integers, (i,a), which indicates the a-th synchronization operation of pi. The inter-process edges are of two types; one from an acquire operation to a release operation; and the other is from an acquire operation to another acquire operation. Each release operation of pi followed by any write can uniquely be identified by the i-th entry of Vi (Vi[i]), however, each acquire operation may not be distinguishable. Hence, in the proposed scheme, the i-the entry of Vi is also incremented by one at each acquire operation. The revised clocks do not violate the semantics of the vector clock[2]. The causal logging can be completed by inserting an interval entry for each acquire operation, which contains the pair, (i,a), indicating that the lock is acquired from pi and pi's current value of Vi[i] is a.


Figure 4.(b) represents the revised write notice structure supporting the causal logging. The vector clock for each acquire operation can be obtained from the structure as we mentioned before. Note here that the obtained vector clock may not be the same as the actual clock since the value of Vi[i] is also incremented for each acquire operation. Hence, the number of acquire operations in each path has to be counted and reflected to the calculated vector clock.


Now, we consider a barrier operation. When a set of processes pass the same barrier, inter-process dependency may happen between every pair of processes, which may make the write notice structure very complicated. To reduce the overhead of recording the precedence relation between every pair of processes, we modify the write notice structure for the barrier operation as shown in Figure 5. The order of the processes in the cycle can be determined by the barrier manager, and we can notice that in both structures shown in Figure 5, the same set of release operations can be obtained for the vector clock calculation.


Theorem 1: The proposed logging protocol ensures that if for each read or write event, ea, an event eb dependent on ea exists, then Log(ea) can be retrieved after a failure.

Proof Sketch: According to the proposed logging protocol, the state interval containing eb must be able to calculate the vector clocks for the interval containing ea and also for the intervals which have generated the data page for the event ea. As a result, Log(ea) can be retrieved after a failure.


  
Figure 5: The Revised Write Notice Structure for Barrier Operation
[IMAGE ]


next up previous
Next: Checkpointing and Rollback-Recovery Up: Protocol Description Previous: Dependency Tracking
Park TaeSoon
1999-11-30