Reasoning with MAD Distributed Systems – Part 1 B


June 5, 2012


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 will review recent results in the theory and practice of building robust MAD systems. In particular we will focus on the BAR (Byzantine, Altruistic, Rational) model, a new failure model that attempts to captures the complexity of MAD systems. We will 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.


Lorenzo Alvisi

Lorenzo Alvisi is a Professor in the Department of Computer Sciences at the University of Texas at Austin and a Visiting Chair Professor at Shanghai Jiao Tong University. Lorenzo holds a Ph.D. (1996) and M.S. (1994) in Computer Science from Cornell University, and a Laurea summa cum laude in Physics from the University of Bologna, Italy. His research interests are in dependable distributed computing. He is a Fellow of the ACM, the recipient of an Alfred P. Sloan Fellowship and an NSF CAREER Award, as well as of several teaching awards. In addition to distributed systems, Lorenzo is passionate about western classical music and red Italian motorcycles.