Using Omissive Faults to Obtain Local Convergence in Partially Connected Networks

Approximate Agreement is an important issue in fault-tolerant distributed computing where non-faulty processes exchange and vote upon their local values, to arrive at values which are within the range of the initial values of the non-faulty processes and within a predefined tolerance of each other. Results to date in Approximate Agreement, however, are not capable of exploiting omission faults. Omission faults are presumed not to occur or a predefined default value is substituted for those values not received, or they are globally discarded before the voting algorithm executes. As a result, hybrid fault models can not differentiate between omissive and transmissive faults. The performance and fault tolerance expressions for completely connected networks, in the presence of omission faults, have recently been obtained. This paper develops a methodology which logically converts partially connected networks into completely connected networks. Hence, the results of completely connected systems can be applied to obtain the local convergence and fault tolerance expressions for partially connected systems