Product Design, Manufacturing & Innovation Resources
Home » Recovery Block Scheme

Recovery Block Scheme

1975-06-01
  • Brian Randell
Software engineer analyzing Recovery Block Scheme in a modern office setting.

(generated image for illustration only)

The recovery block scheme is a software fault-tolerance technique based on design diversity and backward error recovery. It structures a program as a series of blocks, each with a primary module, an acceptance test, and one or more alternate modules. If the primary module’s output fails the acceptance test, the system state is restored, and an alternate module is executed.

The recovery block concept, introduced by Brian Randell, is a structured approach to achieving software fault tolerance. It operates on the principle of providing redundant software modules, known as alternates, for a given operation, coupled with a mechanism to verify the correctness of the operation’s outcome. The key components are: the acceptance test (AT), the primary alternate (P), and a sequence of secondary alternates (Q1, Q2, …). Before executing the primary alternate, the system saves a checkpoint of its current state. Upon completion of P, the acceptance test is run on the output. The AT is a crucial piece of logic that verifies the result is acceptable; it doesn’t need to prove absolute correctness, but rather that the result is reasonable and consistent.

If the result passes the AT, the checkpoint is discarded, and the program proceeds. However, if the AT fails, or if the primary alternate itself fails to execute (e.g., due to a runtime error), the system performs a rollback. It restores the state from the saved checkpoint and then executes the next alternate in the sequence (Q1). The output of Q1 is then subjected to the same acceptance test. This process continues until an alternate produces a result that passes the test, or all alternates have been exhausted, at which point a system-level failure is declared.

The effectiveness of recovery blocks hinges on the diversity of the alternates. The primary and secondary modules should be designed and implemented independently, ideally by different teams using different algorithms or programming languages. This minimizes the chance of a common design flaw (a bug) existing in all alternates, which would cause them all to fail the acceptance test in the same way. The acceptance test itself is a single point of failure and must be simpler and more reliable than the modules it is testing. Compared to N-version programming, another software fault tolerance technique, recovery blocks can be more efficient as they only execute one module at a time, but they introduce latency due to the potential for rollback and re-execution.

UNESCO Nomenclature: 1203
– Computer science

Type

Software/Algorithm

Disruption

Incremental

Usage

Niche/Specialized

Precursors

  • Concepts of exception handling in programming languages
  • Database transaction and rollback mechanisms
  • Early work on program verification and correctness
  • General principles of redundancy from hardware engineering

Applications

  • safety-critical software in railway signaling systems
  • nuclear reactor protection systems
  • aerospace applications where software failure is catastrophic
  • experimental fault-tolerant operating systems

Patents:

NA

Potential Innovations Ideas

Due to scrapping bot traffic, currently more than 40k per day, this content is reserved to community members.
> Login < or > Register < (100% free) to access this, so as all other restricted content and tools.

Related to: recovery blocks, software fault tolerance, design diversity, acceptance test, backward error recovery, checkpointing, Brian Randell, safety-critical software, redundant modules, N-version programming.

Historical Context

Recovery Block Scheme

1970
1970
1970-01-01
1975-06-01
1980
1980
1980
1970
1970
1970
1973
1980
1980
1980
1982-07-01

(if date is unknown or not relevant, e.g. "fluid mechanics", a rounded estimation of its notable emergence is provided)

Related Invention, Innovation & Technical Principles

Full size images and downloads are only available, 100% free, for registered members.

> Login <