Decentralized approaches spanning multiple administrative domains (MAD) are an increasingly effective way to deploy services. Popular examples include peer-to-peer (p2p) applications, content distribution networks, and mesh routing protocols. Cooperation lies at the heart of these services. Yet, when working together is crucial, a natural question is: “What if users stop cooperating?” After all, users in a MAD system are vulnerable not only to the failure of some of the equipment in the system, or to the possibility that some users may behave maliciously, but also to the possibility that users may selfishly refrain from sharing their resources as the protocol would require.
In this setting, it is hard to put a bound on the number of components in the systems that deviate from their correct specification. is it still possible under such circumstances to build systems that not only provide provable guarantees in terms of their safety and liveness properties but also yield practical performance?
In this tutorial, we review recent results in the theory and practice of building robust MAD systems. In particular we focus on the BAR (Byzantine, Altruistic, Rational) model, a new failure model that attempts to captures the complexity of MAD systems. We consider the different approaches that have been proposed to provide a theoretical foundation to BAR fault tolerance, and discuss the design tradeoffs and performance characteristics of BAR fault-tolerant systems.