Crash Fault Identification of a A K-Connected Network in Static Fault Environment

Giri, Sourav Kumar and Panigrahi, Rajeeb Kumar (2009) Crash Fault Identification of a A K-Connected Network in Static Fault Environment. BTech thesis.



The problem of distributed diagnosis in the presence of dynamic failures and repairs is considered. To address this problem, the notion of bounded correctness is defined. Bounded correctness is made up of three properties: bounded diagnostic latency, which ensures that information about state changes of nodes in the system reaches working nodes with a bounded delay, bounded start-up time, which guarantees that working nodes determine valid states for every other node in the system within bounded time after their recovery, and accuracy, which ensures that no spurious events are recorded by working nodes. It is shown that, in order to achieve bounded correctness, the rate at which nodes fail and are repaired must be limited. This requirement is quantified by defining a minimum state holding time in the system. Algorithm HeartbeatComplete is presented and it is proven that this algorithm achieves bounded correctness in fully-connected systems while simultaneously minimizing diagnostic latency, start-up time, and state holding time. A diagnosis algorithm for arbitrary topologies, known as Algorithm ForwardHeartbeat, is also presented.ForwardHeartbeat is shown to produce significantly shorter latency and state holding time than prior algorithms, which focusedprimarily on minimizing the number of tests at the expense of latency.

Item Type:Thesis (BTech)
Uncontrolled Keywords:Crash, Bounded Correctness
Subjects:Engineering and Technology > Computer and Information Science > Networks
Divisions: Engineering and Technology > Department of Computer Science
ID Code:379
Deposited By:Sourav Giri
Deposited On:14 May 2009 10:29
Last Modified:14 Jun 2012 09:51
Supervisor(s):Khilar, P M

Repository Staff Only: item control page