Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2009-08-17
Computer Science
Distributed, Parallel, and Cluster Computing
Shorter version to appear in SSS09
Scientific paper
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 non-crashed processes "fire" simultaneously if some correct process received an external "GO" input, and that they only fire as a response to some process receiving such an input. This paper presents FireAlg, the first self-stabilizing firing squad algorithm. The FireAlg 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.
Dolev Danny
Hoch Ezra N.
Moses Yoram
No associations
LandOfFree
An Optimal Self-Stabilizing Firing Squad does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Optimal Self-Stabilizing Firing Squad, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Optimal Self-Stabilizing Firing Squad will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-19215