Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Leveraging Altruism in Cooperative Services

Jean-Philippe Martin


When there is no central administrator to control the actions of nodes in a distributed system, the users may deviate for personal gain. The BAR model describes the three types of nodes in these environments: Byzantine nodes deviate arbitrarily, Altruistic nodes follow the protocol, and Rational nodes deviate for gain. Previous attempts at writing BAR-Tolerant protocols have relied on a form of policing that makes sure that all non-Byzantine nodes follow the same protocol. This method makes it impossible to take advantage of the Altruistic nodes. In this paper we introduce a new equilibrium concept that does not rely on such strong policing. As a result, we can leverage Altruistic nodes when they are present. We give a condition that is sufficient to ensure that protocol guarantees hold despite Rational and Byzantine nodes, and we show how to use the new equilibrium concept and condition to build a BAR-Tolerant Terminating Reliable Broadcast protocol. Our protocol leverages Altruistic nodes to reduce the amount of extra work that Byzantine nodes can inflict on the system.


Publication typeTechReport
InstitutionMicrosoft Research
> Publications > Leveraging Altruism in Cooperative Services