Lineage management for networks of varying reliability

In distributed and grid applications, complex work dependencies may build between machines during execution and the occurrence of faults may have a detrimental impact on the execution profile. An efficient fault tolerance policy should aim to reduce this impact, whilst taking into account the varying reliability of machines and sites taking part in the computation. This paper proposes a Lineage Management algorithm to protect the work dependency topology. This is accomplished by combining processor replacement mechanisms with data retention "housekeeping" on participating machines. The number of concurrent faults catered for is linearly dependent on the amount of housekeeping performed. This housekeeping "throttle" can then be adjusted from machine to machine in accordance with the reliability of machines or sites.