A Priority-Based Consensus Protocol

Abstract. Consensus is a basic agreement problem whose solutions are funda-mental 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 prob-lem is revisited taking into consideration that the system provides a priority-based communication network. It is shown that for those systems the message transmission time bound can be relaxed so that all but the highest priority mes-sages may be arbitrarily delayed or even lost. The derived consensus protocol can also cope with process crashes, processes may start executing the proto-col 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. 1