My main research interests are distributed computing and fault
tolerance, but I look at computer security and software engineering on
my spare time. This page presents the recent projects I have been
working on, with a brief explanation. You can also jump directly to the publications page. That page, in
addition to being more concise, also includes the abstracts and bibtex
info for the papers.
My thesis focuses on trustworthy systems: systems that do exactly what you want, and nothing more. These systems tolerate
buggy, selfish, or malicious
nodes. I use replication and Byzantine fault tolerant (BFT) protocols to
mask incorrect behaviors.
The main results fall into two broad categories.
Reducing the cost/increasing the performance of BFT systems
Broadening the applicability of BFT protocols
This page also presents some older work.
Large fault-tolerant systems typically cross administrative
boundaries, especially in the case of peer-to-peer or cooperative
applications. In
this case, the traditional Byzantine model is no longer appropriate
and a new model is needed to take into account the fact that the
participants may deviate from the protocol when acting in their
self-interest. The problem is not that Byzantine failures are not
general enough, but rather that they are too general: we know
that no protocol can tolerate a majority of Byzantine nodes, yet in a
multi-administrative-domain deployment it is in fact possible that a
majority of the nodes act for their self-interest and therefore
deviate from the protocol. The question we answer is: how can we get
these self-interested nodes to cooperate?
We propose a principled approach to this problem. First, we introduce a
model, BAR, that specifies for both Byzantine and rational
failures. We use the word "rational" to mean the nodes that may
deviate from the protocol if it is in their self-interest. We
believe that protocols that are designed for deployment over multiple
administrative domains should strive to be BAR-tolerant.
Second, we show how BAR-tolerant protocols can be built. We provide
BAR-tolerant primitives, with which we show how to build a
BAR-tolerant replicated state machine. This replicated state machine
then greatly simplifies the design of BAR-tolerant protocols. As an
illustration, we show a BAR-tolerant cooperative backup application,
BAR-B.
We hope that this paper will encourage more researchers to explore the BAR
model. Our community knows a lot about Byzantine fault-tolerant
protocols, and a lot of real systems are designed to
withstand Byzantine failures. In contrast, all we know of BAR-tolerant
protocols is that there exists at least one (the one we show in the
paper). We hope that real systems of the future will be designed to
withstand not only a minority of Byzantine failures, but also a
majority of rationally-behaving nodes.
What is the minimum possible latency for consensus and the replicated
state machine? In this paper we show that the answer is 2 and 3
communication steps, respectively. While we are not the first to look
at this problem, we are the first (as far as we know) to provide an
asynchronous consensus protocol for unreliable links and Byzantine
failures that can complete in two communication steps (the protocol is
safe in that model, but naturally only live under nicer conditions).
We show that in order to complete in two communication steps despite
failures (a property we call "2-step"), there must be a minimum of
5f+1 processes to tolerate f Byzantine failures. The
cost is fairly high, so we also show a variant (Parameterized FaB)
that can complete in two communication steps with as few as
3f+1 processes (the optimal number of processes). The catch
then is that 2-step operation is only guaranteed if no failure
actually occurs. In order to tolerate f failures and complete
in two communication steps despite t actual failures,
Parameterized FaB requires 3f+2t+1 processors.
When you have a distributed system and a machine fails, you naturally
need to put a new one in its place. What if you want to add machines
to your total, or maybe use a whole new set of servers for your task?
Few systems allow you to change server membership, even though it is
an important concern in practice. If you are using the replicated
state machine approach then it is easy to change server
membership. However, in some cases the state machine approach is too
heavyweight. Almost all lightweight Byzantine fault-tolerant protocols
use the quorums approach.
My advisor and I have determined that it is possible for a
quorum-based protocol to change its servers in a lightweight
manner. Previous attempts required additional servers to enable
dynamism, but we have determined how to do this without adding any
server on top of the minimal number that is necessary to provide
Byzantine fault-tolerant storage in the first place. We have shown how
to do this for a storage system, but we expect that the same technique
can be used on any quorum protocol.
Byzantine failures can model arbitrary failures, so it is natural to
want to use Byzantine-fault-tolerant protocols to tolerate attacks
from crackers. However, BFT protocols require the faults to be
independent. Is is reasonable to say that the fact that a machine was
compromised by a cracker does not give the cracker any advantage in
compromising further machines?
Clearly, if the same bug is present on several machines then the
failures are not independent: either the cracker can compromise no
machine or he can compromise them all. Literature suggests that different
implementations of the application and the operating system should be
used, but we do not know for sure whether this is sufficient. On one
hand, some evidence suggests that even independently developed software
tends to exhibit the same bugs. On the other hand, authors claim that
if the various versions are developed using different techniques then
the failures will be "less" correlated.
I provide a bibliography on
Byzantine fault independence to help other researchers interested in this question. It is not complete, so
if you have corrections or suggestions for addition please contact me. The tools I used to put together
this bibliography are also available.
In this work, we revisit the traditional approach to replicated state
machines (replicated state machines are used to build fault-tolerant
systems). We show that the RSM should be split into two parts:
agreement and execution. The first part generates a unique sequence
from the requests sent to the RSM, and the second part executes the
requests.
This separation allows for a better understanding of RSM, but they
also have the direct practical impact of showing how one can build a
RSM using only 2f+1 execution replicas (to tolerate
f Byzantine faults) instead of the 3f+1 required by
previous approaches, thus saving cost.
The separation also makes it easier to get more out of replicated
state machines. The privacy firewall described below follows directly
from the separation of agreement and execution.
Traditionally, redundancy is used to improve either the performance or
the availability of services. When the servers contain confidential
information, the additional servers introduced by redundancy make it
more likely that an attacker would be able to find a server with a
vulnerability he knows how to exploit.
We are exploring how to use redundancy in a novel way to build
"privacy firewalls" that protect the confidentiality of replicated
data. In particular, we are experimenting with an intrusion-tolerant
nfs that enforces the access rights to files even if some machines
have been compromised.
Hortum is a new and efficient distributed storage protocol that tolerates
Byzantine failures. In other words, Hortum makes it possible to store
data "on the network" in such a way that it can be recovered
(automatically) even if several servers on the network are not
reachable or have been hacked into (i.e. are actively trying to defeat
the storage system).
In the course of this research we have submitted two papers to
conferences. The corresponding publications and technical reports are
available:
Contact me for more information.
Dr Alvisi
and Dr Dahlin are my advisors for this research.
GenBorg describes a novel approach to writing reusable components and
presents a formal algebra for manipulating these components. The goal
is to make it easier to extend software and customize it by removing
functionality that is not needed (to reduce memory usage and improve
performance).
Contact me for more information.
Dr Batori
was my advisor for this research.
Fault-tolerant protocols exist, but they do not scale enough for the
very large clusters in use today. In this paper we explore the
existing protocols, show why they do not scale and propose
compiler-assisted methods to improve scalability.
Download the paper (postscript, 270k).
This paper was a collaborative effort of JP
Martin, Erik Reeber and
Alison N. Smith,
under the direction of Dr Alvisi and Dr Lin.
Torpedo is a web-based network management tool for application
service providers (ASP) which facilitates the task of installing and
managing applications. Torpedo uses ICorpMaker, a tool developed at
IBM. I wrote Torpedo during a summer internship at IBM Zürich.
Download Torpedo-report.ps.gz
(postscript, 2.3M)
Contact me for more information.
Dr Feridun and
Dr Rooney from the Distributed Systems and Network Management division at the
IBM Zurich Research Lab were my supervisors for this project.
Bebop is a software verification tool developed by T. Ball and S. Rajamanii of Microsoft Research. I wrote a paper which describes Bebop and presents an extension for checking arbitrary conditions in nonterminating programs (as opposed to terminating programs only).
Contact me for more information or a copy of the paper.
Dr Emerson was my professor for this project.
If you are looking for the LASR student-organized seminars, please go
to EasyMondays.
[JP Martin]
[publications]
[contact information]
