AN OPTIMAL SELF-STABILIZING FIRING SQUAD

作者：Dolev Danny^*; Hoch Ezra N; Moses Yoram

来源：SIAM Journal on Computing, 2012, 41(2): 415-435.

DOI：10.1137/090776512

• distributed algorithms
• firing squad
• self-stabilization
• synchronous system
• common knowledge
• simultaneity

Consider a fully connected network where up to t processes may crash and all processes start in an arbitrary memory state. The self-stabilizing firing squad problem consists of eventually guaranteeing simultaneous response to an external input. This is modeled by requiring that the noncrashed processes %26quot;fire%26quot; simultaneously if some correct process received an external %26quot;GO%26quot; input, and that they only fire as a response to some process receiving such an input. This paper presents FIRESQUAD, the first self-stabilizing firing squad algorithm. A firing squad algorithm facilitates the use of algorithms that need to start in the same round. It allows a smooth transition between algorithms whose executions need to be disjoint. The FIRESQUAD algorithm combines two forms of fault-tolerance properties: self-stabilization to allow recovery from arbitrary transient errors and resilience to crash failures to handle permanent ones. The FIRESQUAD algorithm is optimal in two respects: (a) once the algorithm is in a safe state, it fires in response to a go input as fast as any other algorithm does, and (b) starting from an arbitrary state, it converges to a safe state as fast as any other algorithm does.

• 出版日期2012