Agreeing on a leader in real-time [fault tolerant computer system]

A method is devised for maintaining the continuing availability of a vital service in a real-time shared-memory multiprocessor fault-tolerant computer system. The essential characteristics of the service to be provided are given. The service can be correctly provided by any one operational processor acting alone. The job of selecting the processor to provide the service is the real-time leader election problem. Two protocols are given 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 complicated and has running time logarithmic in the number of processors. Both protocols use space that is linear in the number of processors