Jean-Philippe Martin | Research | Publications

Some of my recent work. I put together a glossary to act as a reference when reading my papers.
You can also see the page without abstracts, or toggle all.

• Byzantine Fault-Tolerance and Beyond. J-P. Martin. PhD thesis, Dec. 2006. bibtex
  abstract:
  Byzantine fault-tolerance techniques are useful because they tolerate arbitrary faults regardless of cause: bugs, hardware glitches, even hackers. These techniques have recently gained popularity after it was shown that they could be made practical.

  Most of the dissertation builds on Byzantine fault-tolerance (BFT) and extends it with new results for Byzantine fault-tolerance for both quorum systems and state machine replication. Our contributions include proving new lower bounds, finding new protocols that meet these bounds, and providing new functionality at lower cost through a new architecture for state machine replication.

  The second part of the dissertation goes beyond Byzantine fault-tolerance. We show that BFT techniques are not sufficient for networks that span multiple administrative domains, propose the new BAR model to describe these environments, and show how to build BAR-Tolerant protocols through our example of a BAR-Tolerant terminating reliable broadcast protocol.

• Fast Byzantine Consensus. J-P. Martin and L. Alvisi. IEEE Transactions on Dependable and Secure Computing 3(3):202-215, July-Sept. 2006. pdf (preprint) bibtex
  abstract:
  We present the first protocol that reaches asynchronous Byzantine consensus in two communication steps in the common case. We prove that our protocol is optimal in terms of both number of communication steps, and number of processes for 2-step consensus. The protocol can be used to build a replicated state machine that requires only three communication steps per request in the common case. Further, we show a parameterized version of the protocol that is safe despite f Byzantine failures and in the common case guarantees 2-step execution despite some number t of failures (t ≤ f). We show that this parameterized 2-step consensus protocol is also optimal in terms of both number of communication steps, and number of processes.

• BAR Fault Tolerance for Cooperative Services. A. Aiyer, L. Alvisi, A. Clement, M. Dahlin, J-P. Martin, and C. Porth. 20th Symposium on Operating Systems Principles (SOSP 2005), October 2005. pdf bibtex slides (award paper)
  abstract:
  This paper 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. The paper makes three contributions: (1) It introduces the BAR (Byzantine, Altruistic, Rational) model as a foundation for reasoning about cooperative services; (2) It proposes a general three-level architecture to reduce the complexity of building services under the BAR model; and (3) It describes 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 100 MB of data in under 4 minutes.

• Fast Byzantine Consensus. J-P. Martin and L. Alvisi. 2005 International Conference on Dependable Systems and Networks (DSN 2005), June 2005. pdf bibtex (award paper)
  abstract:
  We present the first consensus protocol that reaches asynchronous Byzantine consensus in two communication steps in the common case. We prove that our protocol is optimal in terms of both number of communication step, and number of processes for 2-step consensus. The protocol can be used to build a replicated state machine that requires only three communication steps per request in the common case.

• A Framework for Dynamic Byzantine Storage (extended technical report) J-P. Martin and L. Alvisi. The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-04-08. January 2004. ps

• A Framework for Dynamic Byzantine Storage. J-P. Martin and L. Alvisi. 2004 International Conference on Dependable Systems and Networks (DSN 2004), June 2004. ps pdf bibtex. Slides from DSN'04, June 2004 (pdf pdb).
  abstract:
  We present a framework for transforming several quorum-based protocols so that they can dynamically adapt their failure threshold and server count, allowing them to be reconfigured in anticipation of possible failures or to replace servers as desired. We demonstrate this transformation on the dissemination quorum protocol. The resulting system provides confirmable wait-free atomic semantics while tolerating Byzantine failures from the clients or servers. The system can grow without bound to tolerate as many failures as desired. Finally, the protocol is optimal and fast: only the minimal number of servers ---3f+1--- is needed to tolerate any f failures and, in the common case, reads require only one message round-trip.

• Fast Byzantine Paxos (extended technical report) J-P. Martin and L. Alvisi. The University of Texas at Austin, Department of Computer Sciences. Technical Report TR-04-07. February 2004. ps bibtex. Slides from SOS'04, June 23-25, 2004 (pdf pdb).
  abstract:
  We present the first Byzantine Paxos protocol to achieve consensus in just two communication steps in the common case and discuss how it can be used to implement a fast Byzantine fault-tolerant replicated state machine.

• Separating Agreement from Execution for Byzantine Fault Tolerant Services. J. Yin, J-P. Martin, A. Venkataramani, L. Alvisi, M. Dahlin. Proceedings of the 19th Symposium on Operating Systems Principles (SOSP 2003), October 2003. ps pdf bibtex SOSP slides
  abstract:
  We describe a new architecture for Byzantine fault tolerant state machine replication that separates agreement - ordering requests - from execution - processing requests. This separation yields two fundamental and practically significant advantages over previous architectures. First, it reduces replication costs because the new architecture can tolerate faults in up to half of the state machine replicas that execute requests. Previous systems can tolerate faults in at most a third of the combined agreement/state machine replicas. Second, separating agreement from execution allows a general privacy firewall architecture to protect confidentiality through replication. In contrast, replication in previous systems hurts confidentiality because exploiting the weakest replica can be sufficient to compromise the system. We have constructed a prototype and evaluated it running both microbenchmarks and an NFS server. Overall, we find that the architecture adds modest latencies to unreplicated systems and that its performance is competitive with existing Byzantine fault tolerant systems.

• Generating Product-Lines of Product-Families D. Batory, R. Lopez-Herrejon, J-P. Martin. September 2002. ASE 2002. pdf bibtex
  abstract:
  GenVoca is a methodology and technology for generating product-lines, building variants of the same program. The primitive components from which applications are constructed are refinements or layers, which are modules that implement a feature that many programs of a product-line can share. Unlike conventional components (e.g., COM, CORBA, EJB), a layer encapsulates fragments of multiple classes. Sets of fully-formed classes can be produced by composing layers. Layers are modu-lar, albeit unconventional, building blocks of programs.

  But what are the building blocks of layers? We argue that facets is an answer. A facet encapsulates fragments of multiple layers, and compositions of facets yields sets of fully-formed layers. Facets arise when refinements scale from producing variants of individual programs to producing variants of multiple integrated programs, as typified by product families (e.g., MS Office).

  We present a mathematical model that explains relationships between layers and facets. We use the model to develop a generator for tools (i.e., product-family) that are used in language-extensible Integrated Development Environments (IDEs).

• Minimal Byzantine Storage (extended technical report) J-P. Martin, L. Alvisi, M. Dahlin. Technical Report TR-02-38. August 2002 (updated version). ps pdf bibtex
  abstract:
  Byzantine fault-tolerant storage systems can provide high availability in hazardous environments, but the redundant servers they require increase software development and hardware costs. In order to minimize the number of servers required to implement fault-tolerant storage services, we develop a new algorithm that uses a "Listeners" pattern of network communication to detect and resolve ordering ambiguities created by concurrent accesses to the system. When storing generic data, our protocol requires 3f+1 servers to tolerate up to f Byzantine faults - f fewer than the 4f+1 required by existing protocols for non-self-verifying data. In addition, SBQ-L provides atomic consistency semantics, which is stronger than the regular or pseudo-atomic semantics provided by these existing protocols. We show that this protocol is optimal in the number of servers - any protocol that provides safe semantics or stronger requires at least 3f+1 servers to tolerate f Byzantine faults in an asynchronous system. We also examine protocols that store self-verifying data (i.e. data that cannot be undetectably altered). Existing protocols can use self-verifying data to reduce the number of servers required to tolerate faults but because SBQ-L already uses the minimum possible number of servers for its semantics, self-verifying data provides no advantage. Finally, we examine a non-confirmable writes variation of the SBQ-L protocol where a client cannot determine when its writes complete. We show that SBQ-L with non--confirmable writes provides regular semantics with 2f+1 servers and that this number of servers is minimal.

• Minimal Byzantine Storage J-P. Martin, L. Alvisi, M. Dahlin. Proceedings of the 16th International Symposium on Distributed Computing (DISC 2002). Toulouse, France. LNCS 2508 pp 311-325. ISBN 3-540-00073-9. ps pdf bibtex slides
  abstract:
  Byzantine fault-tolerant storage systems can provide high availability in hazardous environments, but the redundant servers they require increase software development and hardware costs. In order to minimize the number of servers required to implement fault-tolerant storage services, we develop a new algorithm that uses a "Listeners" pattern of network communication to detect and resolve ordering ambiguities created by concurrent accesses to the system. When storing generic data, our protocol requires 3f+1 servers to tolerate up to f Byzantine faults - f fewer than the 4f+1 required by existing protocols for non-self-verifying data. In addition, SBQ-L provides atomic consistency semantics, which is stronger than the regular or pseudo-atomic semantics provided by these existing protocols. We show that this protocol is optimal in the number of servers - any protocol that provides safe semantics or stronger requires at least 3f+1 servers to tolerate f Byzantine faults in an asynchronous system. We also examine protocols that store self-verifying data (i.e. data that cannot be undetectably altered). Existing protocols can use self-verifying data to reduce the number of servers required to tolerate faults but because SBQ-L already uses the minimum possible number of servers for its semantics, self-verifying data provides no advantage. Finally, we examine a non-confirmable writes variation of the SBQ-L protocol where a client cannot determine when its writes complete. We show that SBQ-L with non--confirmable writes provides regular semantics with 2f+1 servers and that this number of servers is minimal.

• Byzantine Fault-Tolerant Confidentiality (updated) J. Yin, J-P. Martin, A. Venkataramani, L. Alvisi, M. Dahlin. LNCS 2584, 2003. pp. 51-56 ps pdf bibtex

• Fault-Tolerance and Security (when opposites attract) J. Yin, A. Venkataramani, J-P. Martin, L. Alvisi, M. Dahlin. slides from FuDiCo 2002 (pdf).

• Minimal Byzantine Quorum Systems (extended technical report) J-P. Martin, L. Alvisi, M. Dahlin. February 2002. ps bibtex NOTE: This paper is superseded by "Minimal Byzantine Storage", above.

• Small Byzantine Quorum Systems J-P. Martin, L. Alvisi, M. Dahlin. Proceedings of the 2002 International Conference on Dependable Systems & Networks (DSN 2002). pages 374-383. ps pdf bibtex
  abstract:
  In this paper we present two protocols for asynchronous Byzantine Quorum Systems (BQS) built on top of reliable channels -- one for self-verifying data and the other for any data. Our protocols tolerate f Byzantine failures with f fewer servers than existing solutions by eliminating nonessential work in the write protocol and by using read and write quorums of different sizes. Since engineering a reliable network layer on an unreliable network is difficult, two other possibilities must be explored. The first is to strengthen the model by allowing synchronous networks that use time-outs to identify failed links or machines. We consider running synchronous and asynchronous Byzantine Quorum protocols over synchronous networks and conclude that, surprisingly, "self-timing" asynchronous Byzantine protocols may offer significant advantages for many synchronous networks when network time-outs are long. We show how to extend an existing Byzantine Quorum protocol to eliminate its dependency on reliable networking and to handle message loss and retransmission explicitly.

• Small Byzantine Quorum Systems (extended technical report) J-P. Martin, L. Alvisi, M. Dahlin. Technical Report TR-02-01. January 2002. ps pdf bibtex
  abstract:
  In this paper we present two protocols for asynchronous Byzantine Quorum Systems (BQS) built on top of reliable channels -- one for self-verifying data and the other for any data. Our protocols tolerate f Byzantine failures with f fewer servers than existing solutions by eliminating nonessential work in the write protocol and by using read and write quorums of different sizes. Since engineering a reliable network layer on an unreliable network is difficult, two other possibilities must be explored. The first is to strengthen the model by allowing synchronous networks that use time-outs to identify failed links or machines. We consider running synchronous and asynchronous Byzantine Quorum protocols over synchronous networks and conclude that, surprisingly, "self-timing" asynchronous Byzantine protocols may offer significant advantages for many synchronous networks when network time-outs are long. We show how to extend an existing Byzantine Quorum protocol to eliminate its dependency on reliable networking and to handle message loss and retransmission explicitly.

• On Checking Temporal Properties of Software with Boolean Programs J-P. Martin. December 2000. ps
  abstract:
  This document describes the approach to model checking of software programs suggested by T. Ball and S. Rajamani with their "Bebop" model checker. This approach is novel in that it allows fast checking of terminating programs, even if they include procedure calls or recursion. An extension to this model check is then described. This extension allows the checking of arbitrary conditions for nonterminating programs, while still supporting procedure calls and recursion. Finally, some open questions are presented.