Rational Uniform Consensus with General Omission Failures
share
Generally, system failures, such as crash failures, Byzantine failures and so on, are considered as common reasons for the inconsistencies of distributed consensus and have been extensively studied. In fact, strategic manipulations by rational agents do not be ignored for reaching consensus in distributed system. In this paper, we extend the game-theoretic analysis of consensus and design an algorithm of rational uniform consensus with general omission failures under the assumption that processes are controlled by rational agents and prefer consensus. Different from crashing one, agent with omission failures may crash, or omit to send or receive messages when it should, which leads to difficulty of detecting faulty agents. By combining the possible failures of agents at the both ends of a link, we convert omission failure model into link state model to make faulty detection possible. Through analyzing message passing mechanism in the distributed system with n agents, among which t agents may commit omission failures, we provide the upper bound on message passing time for reaching consensus on a state among nonfaulty agents, and message chain mechanism for validating messages. And then we prove our rational uniform consensus is a Nash equilibrium when n>2t+1, and failure patterns and initial preferences are blind (an assumption of randomness). Thus agents could have no motivation to deviate the consensus. Our research strengthens the reliability of consensus with omission failures from the perspective of game theory.
READ FULL TEXT