BAR primer

Byzantine and rational behaviors are increasingly recognized as unavoidable realities in todaypsilas cooperative services. Yet, how to design BAR-tolerant protocols and rigorously prove them strategy proof remains somewhat of a mystery: existing examples tend either to focus on unrealistically simple problems or to want in rigor. The goal of this paper is to demystify the process by presenting the full algorithmic development cycle that, starting from the classic synchronous repeated terminating reliable broadcast (R-TRB) problem statement, leads to a provably BAR-tolerant solution. We show i) how to express R-TRB as a game; ii) why the strategy corresponding to the optimal Byzantine fault tolerant algorithm of Dolev and strong does not guarantee safety when non-Byzantine players behave rationally; iii) how to derive a BAR-tolerant R-TRB protocol: iv) how to prove rigorously that the protocol ensures safety in the presence of non-Byzantine rational players.

1 Introduction

Cooperative services are increasingly popular distributed systems in which nodes belong to multiple administrative domains (MADs). Examples of MAD distributed systems include Internet routing [8], [17], wireless mesh routing [13] and peer-to-peer services [2], [5].