A Priority-based Consensus Protocol

Consensus is a basic agreement problem whose solutions are fundamental for building fault-tolerant distributed systems. Consensus for real-time systems is usually designed under strong timing assumptions, which state that there are upper bounds on both processing and message transmission times. Since violating these bounds may compromise safety, such systems are usually implemented based on pessimistic bounds. In this paper the consensus problem is revisited taking into consideration that the system provides a prioritybased communication network. It is shown that for those systems the message transmission time bound can be relaxed so that all but the highest priority messages may be arbitrarily delayed or even lost. The derived consensus protocol can also cope with process crashes, processes may start executing the protocol asynchronously, and consensus is reached within a known bounded time. These characteristics make the proposed solution very interesting to real-time systems. The protocol is proved correct and analyzed by simulation. Since there are a number of priority-based networks, the results presented here have both theoretical and practical implications.