Agreeing on a Leader in Real-Time.
Brian Coan, Gomer Thomas · Real-Time Systems Symposium · 1990
We devise a method for maintaining the con- tinuing availability of a vital service in a real-time shared- memory multi-processor fault-tolerant computer system. The essential characteristics of the service to be provided are given by the following four properties. (1) The ser- vice can be correctly provided by any one operational processor acting alone, but an error will result if multi- ple operational processors attempt to provide the service simultaneously. (2) If some processor ceases to provide the service (because of failure or for any other reason), its job can be taken over by any other processor without causing an error. (3) Even in the presence of processor failures, there should almost always be some operational processor that is providing the service and whose identity is known to the other operational processors. (4) There should be a known upper bound on the duration of any service outage that can be caused by any single processor failure or recovery. The job of selecting the processor to provide the service is the real-time leader election prob- lem. In this paper we give two protocols which solve this problem in shared-memory systems. Each tolerates the failure of any subset of the processors. The first protocol is extremely simple and has running time linear in the number of processors. The second is slightly more com- plicated and has running time logarithmic in the number of processors. Both protocols use space that is linear in the number of processors.