next up previous
Next: Dependency Tracking Up: Protocol Description Previous: Protocol Description

Overview


Causal logging is one way to achieve the consistent recovery. Let Log(ek) be the information logged to regenerate the exactly same event ek. Under the assumption of the piece-wise deterministic computation, if Log(ek) for every read and write event, which may cause the potential orphan state, can be retrieved at the time of rollback-recovery, the consistent recovery can be guaranteed. For the correct regeneration of an event, Log(ek) must include the data page which have been provided for the event ek, the identifier of the write event which creates that page and the identifier of the event ek. The causal logging consists of two parts; one is the writer-based logging of the data page contents, and the other is the causal logging of the data access information, such as the event identifiers, by the dependent processes.


For logging of the data pages, the diff structure maintained by each process can be utilized, since the diff can be regenerated from a correct recovery even after a system failure. As for the event identifiers to trace the data access, the vector clock associated with each synchronization operation can be used. Figure 2 shows an example of vector clocks associated with each synchronization operation. Note from the figure that if each process knows the vector clock of its current state interval and accesses the page made from the diffs created at the intervals with smaller vector clocks, then the consistent recovery can be achieved [7].


  
Figure 2: An Example of Vector Clocks
[IMAGE ]


To causally log the vector clocks, the operations handling the write notice structures can be used. One notable point of write notice handling operations is that the write notice records are causally propagated to the processes in the dependency relation. Another notable point is that the propagation is not redundant. If a write notice record is propagated to a process, the same record is not delivered to the same process, again. The write notices, however, reflect only the information regarding the write operations. In other words, only the vector clocks for release operations following any write operation are included in the write notices. Hence, the write notice structure needs to be slightly modified so that the vector clock for each synchronization operation can be reflected in the structure.


However, considering the size of the vector clock, it is more efficient to save some information to recreate the vector clock, instead of saving the vector clock itself. Hence, in the proposed protocol, for each synchronization operation, the sufficient and necessary information to recreate the corresponding vector clock is inserted into the write notice structure.


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