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 p_i. 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 p_i followed by any write can uniquely be identified by the i-th entry of V_i (V_i[i]), however, each acquire operation may not be distinguishable. Hence, in the proposed scheme, the i-the entry of V_i 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 p_i and p_i's current value of V_i[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 V_i[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, e_a, an event e_b dependent on e_a exists, then Log(e_a) can be retrieved after a failure.

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

  

Figure 5: The Revised Write Notice Structure for Barrier Operation

[IMAGE ]