8.2.1
Uncoordinated Recovery Points . . . . . . . . . . . . . . . . 117
8.2.2
Coordinated Recovery Points . . . . . . . . . . . . . . . . . . 117
8.2.3
Message Logging-Based Rollback Recovery . . . . . . . 119
8.2.4
Other Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . 120
8.2.5
Implementation Aspects . . . . . . . . . . . . . . . . . . . . . 121
8.3
Recovery at the Level of Procedures . . . . . . . . . . . . . . . . . . . 122
8.4
Hardware Support for Recovery Point Creation . . . . . . . . . . . . 123
8.5
Variable Recovery Point Creation . . . . . . . . . . . . . . . . . . . . . 125
8.5.1
Efficiency Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 126
8.6
Implementation Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
8.7
Ultrareliable Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8.7.1
Physical Storage Media . . . . . . . . . . . . . . . . . . . . . . 131
8.7.2
Flash Properties and Limitations . . . . . . . . . . . . . . . 132
8.7.3
Analysis and Design Considerations . . . . . . . . . . . . 133
8.7.4
Implementation Aspects . . . . . . . . . . . . . . . . . . . . . 134
8.8
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
9 Recovery: Searching and Monitoring of Correct
Software States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
9.1
Recovery as a Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
9.2
Modified Linear Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 143
9.2.1
Characteristics of Modified Linear Recovery
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
9.2.2
MLR Execution in Case of Permanent Faults . . . . . . 146
9.2.3
The MLR Algorithm in Case of Several Successive
Faults in Case of Permanent Faults . . . . . . . . . . . . . 149
9.2.4
Hardware Support for the MLR Algorithm . . . . . . . . 150
9.3
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
10 Recovery Algorithms: An Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 153
10.1 Comparison of MLR and Two Other Recovery Algorithms
of the Same Family . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
10.2 Computational Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
10.3 Linear Recovery Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 155
10.4 Dichotomous Recovery Algorithm . . . . . . . . . . . . . . . . . . . . . 159
10.5 Modified Linear Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
10.6 Conclusion on Comparison of Recovery Algorithms . . . . . . . . 162
10.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Contents
xiii
Uncoordinated Recovery Points . . . . . . . . . . . . . . . . 117
8.2.2
Coordinated Recovery Points . . . . . . . . . . . . . . . . . . 117
8.2.3
Message Logging-Based Rollback Recovery . . . . . . . 119
8.2.4
Other Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . 120
8.2.5
Implementation Aspects . . . . . . . . . . . . . . . . . . . . . 121
8.3
Recovery at the Level of Procedures . . . . . . . . . . . . . . . . . . . 122
8.4
Hardware Support for Recovery Point Creation . . . . . . . . . . . . 123
8.5
Variable Recovery Point Creation . . . . . . . . . . . . . . . . . . . . . 125
8.5.1
Efficiency Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 126
8.6
Implementation Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
8.7
Ultrareliable Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
8.7.1
Physical Storage Media . . . . . . . . . . . . . . . . . . . . . . 131
8.7.2
Flash Properties and Limitations . . . . . . . . . . . . . . . 132
8.7.3
Analysis and Design Considerations . . . . . . . . . . . . 133
8.7.4
Implementation Aspects . . . . . . . . . . . . . . . . . . . . . 134
8.8
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
9 Recovery: Searching and Monitoring of Correct
Software States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
9.1
Recovery as a Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
9.2
Modified Linear Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 143
9.2.1
Characteristics of Modified Linear Recovery
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
9.2.2
MLR Execution in Case of Permanent Faults . . . . . . 146
9.2.3
The MLR Algorithm in Case of Several Successive
Faults in Case of Permanent Faults . . . . . . . . . . . . . 149
9.2.4
Hardware Support for the MLR Algorithm . . . . . . . . 150
9.3
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
10 Recovery Algorithms: An Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 153
10.1 Comparison of MLR and Two Other Recovery Algorithms
of the Same Family . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
10.2 Computational Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
10.3 Linear Recovery Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 155
10.4 Dichotomous Recovery Algorithm . . . . . . . . . . . . . . . . . . . . . 159
10.5 Modified Linear Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
10.6 Conclusion on Comparison of Recovery Algorithms . . . . . . . . 162
10.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Contents
xiii