Invited Talk Series: Computer Information Assurance and Security

Friday, November 18, 2005
2:00-3:30 p.m.
Bioscience Building, Loeffler Room 3.03.02

Reasoning with MAD Distributed Systems

Lorenzo Alvisi
Associate Professor
University of Texas at Austin

Abstract: Distributed services spanning multiple administrative domains (MADs) have become increasingly popular. In a MAD distributed service, nodes collaborate to provide some service that benefits each node, but there is no central authority that controls the nodes' actions. Examples of such services include Internet routing, wireless mesh routing, file distribution, archival storage, and cooperative backup.

Unfortunately, there currently exists no satisfactory way to model MAD services. In these systems, the classical dichotomy between correct and faulty nodes becomes inadequate. Nodes in MAD systems may depart from protocols for two distinct reasons. First, as in traditional systems, nodes may be broken and arbitrarily deviate from a protocol because of component failure, misconfiguration, security compromise, or malicious intent. Second, nodes may be selfish and alter the protocol in order to increase their utility. Byzantine Fault Tolerance (BFT) handles the first class of deviations well. However, the Byzantine model classifies all deviations as faults and requires a bound on the number of faults in the system; this bound is not tenable in MAD systems where all nodes may benefit from selfish behavior and be motivated to deviate from the protocol. Models that only account for rational behavior handle the second class of selfish deviations, but may be vulnerable to arbitrary disruptions if even a single node is broken and deviates from expected rational behavior.

As MAD distributed systems become more commonplace, it becomes increasingly important to develop a solid foundation for constructing this class of services. The challenge is (at least) threefold:

1. to develop a model for MAD services in which it is possible to prove that a given MAD service meets its goals, no matter what strategies nodes may concoct within the scope of the adversary model.
2. to demonstrate that MAD services developed under this model can be practical.
3. to understand how to simplify the development of MAD services under the new model.

This talk will describe our preliminary answers to these challenges.

Bio: Lorenzo Alvisi is an Associate Professor and Faculty Fellow in the Department of Computer Sciences at the University of Texas at Austin. 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. Lorenzo received a NSF CAREER Award in 1998 and an Alfred P. Sloan Fellowship in 2001. He is interested in distributed systems, fault-tolerance, security, and red Italian motorcycles.