DATE: Wednesday, August 24, 2005 Note Special Day
TIME: 12:30 pm - 1:30 pm Note Special Time

Lorenzo Alvisi
University of Texas, Austin

BAR Fault Tolerance for Cooperative Services

This talk describes a general approach to constructing cooperative services that span multiple administrative domains. In such environments, protocols must tolerate both Byzantine behaviors when broken, misconfigured, or malicious nodes arbitrarily deviate from their specification and rational behaviors when selfish nodes deviate from their specification to increase their local benefit.

We will first introduce the BAR (Byzantine, Altruistic, Rational) model as a foundation for reasoning about cooperative services. We will then proposes a general three-level architecture to reduce the complexity of building services under the BAR model. Finally, we will describe an implementation of BAR-B, the first cooperative backup service to tolerate both Byzantine users and an unbounded number of rational users. At the core of BAR-B is an asynchronous replicated state machine that provides the customary safety and liveness guarantees despite nodes exhibiting both Byzantine and rational behaviors. Our prototype provides acceptable performance for our application: our BAR-tolerant state machine executes 15 requests per second, and our BAR-B backup service can back up 100MB of data in under 4 minutes.

Lorenzo Alvisi is an Associate Professor and Faculty Fellow in the Department of Computer Sciences at the University of Texas at Austin and an Alfred P. Sloan Research Fellow. He 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. He is interested in distributed systems, dependability, and red Italian motorcycles.

For Further Seminar Info Contact:
or visit