HQ Replication: Properties and Optimizations (2007)
Cowling, James, Myers, Daniel, Liskov, Barbara, Rodrigues, Rodrigo, Shrira, Liuba
There are currently two approaches to providing Byzantine-fault-tolerant state machine replication: a replica-based approach, e.g., BFT, that uses communication between replicas to agree on a...
HQ Replication: Properties and Optimizations (2007)
Cowling, James, Myers, Daniel, Liskov, Barbara, Rodrigues, Rodrigo, Shrira, Liuba
There are currently two approaches to providing Byzantine-fault-tolerant state machine replication: a replica-based approach, e.g., BFT, that uses communication between replicas to agree on a...
Automatic Software Upgrades for Distributed Systems (2005)
Ajmani, Sameer, Liskov, Barbara, Shrira, Liuba, Curtis, Dorothy
Upgrading the software of long-lived, highly-available distributedsystems is difficult. It is not possible to upgrade all the nodes in asystem at once, since some nodes may be unavailable and halting...
Automatic Software Upgrades for Distributed Systems (2005)
Ajmani, Sameer, Liskov, Barbara, Shrira, Liuba, Curtis, Dorothy
Upgrading the software of long-lived, highly-available distributedsystems is difficult. It is not possible to upgrade all the nodes in asystem at once, since some nodes may be unavailable and halting...
Byzantine Clients Rendered Harmless (2005)
Liskov, Barbara, Rodrigues, Rodrigo
Byzantine quorum systems have been proposed that work properly even when up to f replicas fail arbitrarily.However, these systems are not so successful when confronted with Byzantine faulty clients....
Byzantine Clients Rendered Harmless (2005)
Liskov, Barbara, Rodrigues, Rodrigo
Byzantine quorum systems have been proposed that work properly even when up to f replicas fail arbitrarily.However, these systems are not so successful when confronted with Byzantine faulty clients....
Argus Reference Manual. (2005)
Liskov, Barbara, Day, Mark, Herlihy, Maurice, Johnson, Paul, Leavens, Gary
Argus is an experimental language/system designed to support the construction and execution of distributed programs. Argus is intended to support only a subset of the applications that could benefit...
Transactional File Systems Can Be Fast (2004)
Barbara Liskov, Rodrigo Rodrigues
Transactions ensure simple and correct handling of concurrency and failures but are often considered too expensive for use in file systems. This paper argues that performance is not a barrier to...
Byzantine Fault Tolerance in Long-Lived Systems (2004)
Rodrigo Rodrigues, Barbara Liskov
this paper is: what can be done to increase the probability that no more than f replicas are faulty simultaneously? We address this question using the following simple model
EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management (2004)
Leong, Ben, Liskov, Barbara, Demaine, Erik D.
EpiChord is a DHT lookup algorithm that demonstrates that we canremove the O(log n)-state-per-node restriction on existing DHTtopologies to achieve significantly better lookup performance...
Byzantine Fault Tolerance in Long-Lived Systems (2004)
Rodrigues, Rodrigo, Liskov, Barbara
This paper proposes counter-measures that can be deployedas part of a replicated system to reduce the size ofW, and thus reduce the class of attacks to which the system is vulnerable. Obviously it...
Byzantine Fault Tolerance in Long-Lived Systems (2004)
Rodrigues, Rodrigo, Liskov, Barbara
This paper proposes counter-measures that can be deployedas part of a replicated system to reduce the size ofW, and thus reduce the class of attacks to which the system is vulnerable. Obviously it...
EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management (2004)
Leong, Ben, Liskov, Barbara, Demaine, Erik D.
EpiChord is a DHT lookup algorithm that demonstrates that we canremove the O(log n)-state-per-node restriction on existing DHTtopologies to achieve significantly better lookup performance...
TimeLine: A High Performance Archive for a Distributed Object Store (2004)
Chuang-hue Moh, Barbara Liskov
This paper describes TimeLine, an e#cient archive service for a distributed storage system. TimeLine allows users to take snapshots on demand. The archive is stored online so that it is easily...
The Design of a Robust Peer-to-Peer System (2004)
Rodrigo Rodrigues, Barbara Liskov, Liuba Shrira
Peer-to-peer (P2P) overlay networks have recently become one of the hottest topics in OS research. These networks bring with them the promise of harnessing idle storage and network resources from...
Ecient Routing for Peer-to-Peer Overlays (2004)
Anjali Gupta, Barbara Liskov, Rodrigo Rodrigues
Most current peer-to-peer lookup schemes keep a small amount of routing state per node, typically logarithmic in the number of overlay nodes. This design assumes that routing information at each...
Brief Announcement: Reconfigurable Zantine-Fault-Tolerant Atomic Memory (2004)
Rodrigo Rodrigues, Barbara Liskov
This paper addresses this limitation by presenting an algorithm for a reconfigurable Byzantine quorum system. Our algorithm ensures atomicity with an asynchronous network despite Byzantine failures...
Sameer Ajmani, Barbara Liskov, Liuba Hrira
Upgrading the software of long-lived distributed systems is difficult. It is not possible to upgrade all the nodes in a system at once, since some nodes may be down and halting the system for an...
Anjali Gupta, Barbara Liskov, Rj Rjst
Current peer-to-peerlo-pe alpeerAWz have been designed with the assumption that routing information at each member node must be keptsmalW so that the bookkeeping required to respond to system...
Brief Announcement: Reconfigurable (2004)
Rodrigo Rodrigues, Barbara Liskov
This paper addresses this limitation by presenting an algorithm for a reconfigurable Byzantine quorum system. Our algorithm ensures atomicity with an asynchronous network despite Byzantine failures...
TimeLine: A High Performance Archive for a Distributed Object Store (2004)
Chuang-hue Moh, Barbara Liskov
This paper describes TimeLine, an efficient archive service for a distributed storage system. TimeLine allows users to take snapshots on demand. The archive is stored online so that it is easily...
B.S., Electrical Engineering and Computer Science (2004)
In this work, we present mechanisms for transparently evolving component implementations in an application while preserving instance consistency. We also describe a runtime system based on the Java...
This paper describes a new replication algorithm that is able to tolerate Byzantine faults. We believe that Byzantinefault -tolerant algorithms will be increasingly important in the future because...
Ecient Routing for Peer-to-Peer Overlays (2004)
Anjali Gupta, Barbara Liskov, Rodrigo Rodrigues
Most current peer-to-peer lookup schemes keep a small amount of routing state per node, typically logarithmic in the number of overlay nodes. This design assumes that routing information at each...
Rosebud: A Scalable Byzantine-Fault-Tolerant Storage Architecture (2003)
Rodrigues, Rodrigo, Liskov, Barbara
This paper presents Rosebud, a new Byzantine faulttolerantstorage architecture designed to be highly scalableand deployable in the wide-area. To support massiveamounts of data, we need to partition...
Rosebud: A Scalable Byzantine-Fault-Tolerant Storage Architecture (2003)
Rodrigues, Rodrigo, Liskov, Barbara
This paper presents Rosebud, a new Byzantine faulttolerantstorage architecture designed to be highly scalableand deployable in the wide-area. To support massiveamounts of data, we need to partition...
Lazy Modular Upgrades in Persistent Object Stores (2003)
Rasekhar Boyapati, Barbara Liskov, Liuba Shrira, Chuang-hue Moh, Steven Richman
Persistent object stores require a way to automatically upgrade persistent objects, to change their code and storage representation. Automatic upgrades are a challenge for such systems. Upgrades must...
Lazy Modular Upgrades in Persistent Object Stores (2003)
Rasekhar Boyapati, Barbara Liskov, Liuba Shrira, Chuang-hue Moh, Steven Richman
Persistent object stores require a way to automatically upgrade persistent objects, to change their code and storage representation. Automatic upgrades are a challenge for such systems. Upgrades must...
Ownership Types for Object Encapsulation (2003)
Chandrasekhar Boyapati, Barbara Liskov, Liuba Shrira
object encapsulation and enable local reasoning about program correctness in object-oriented languages. However, a type system that enforces strict object encapsulation is too constraining: it does...
ACM Symposium on Principles of Programming Languages (POPL), January 2003 (2003)
Chandrasekhar Boyapati, Barbara Liskov, Liuba Shrira
object encapsulation and enable local reasoning about program correctness in object-oriented languages. However, a type system that enforces strict object encapsulation is too constraining: it does...
One Hop Lookups for Peer-to-Peer Overlays (2003)
Anjali Gupta, Barbara Liskov, Rodrigo Rodrigues
Current peer-to-peer lookup algorithms have been designed with the assumption that routing information at each member node must be kept small, so that the bookkeeping required to respond to system...
Rodrigues, Rodrigo, Liskov, Barbara
We prove correctness of a Byzantine-fault-tolerant replication algorithm for a read/writeatomic memory that supports a dynamic replica set.
Rodrigues, Rodrigo, Liskov, Barbara
We prove correctness of a Byzantine-fault-tolerant replication algorithm for a read/writeatomic memory that supports a dynamic replica set.
Scheduling and Simulation: How to Upgrade Distributed Systems (2003)
Sameer Ajmani, Barbara Liskov, Liuba Shrira
Upgrading the software of long-lived distributed systems is difficult. It is not possible to upgrade all the nodes in a system at once, since some nodes may be down and halting the system for an...
One Hop Lookups for Peer-to-Peer Overlays (2003)
Anjali Gupta, Barbara Liskov, Rodrigo Rodrigues
Current peer-to-peer lookup algorithms have been designed with the assumption that routing information at each member node must be kept small, so that the bookkeeping required to respond to system...
Scheduling and Simulation: How to Upgrade Distributed Systems (2003)
Sameer Ajmani, Barbara Liskov, Liuba Shrira
Upgrading the software of long-lived distributed systems is difficult. It is not possible to upgrade all the nodes in a system at once, since some nodes may be down and halting the system for an...
One Hop Lookups for Peer-to-Peer Overlays (2003)
Anjali Gupta, Barbara Liskov, Rodrigo Rodrigues
Current peer-to-peer lookup algorithms have been designed with the assumption that routing information at each member node must be kept small, so that the bookkeeping required to respond to system...
Lazy Modular Upgrades in Persistent Object Stores (2003)
Rasekhar Boyapati, Barbara Liskov, Liuba Shrira, Chuang-hue Moh, Steven Richman
Persistent object stores require a way to automatically upgrade persistent objects. Automatic upgrades are a challenge for such systems. Upgrades must be performed in a way that is efficient both in...
One Hop Lookups for Peer-to-Peer Overlays (2003)
Anjali Gupta, Barbara Liskov, Rodrigo Rodrigues
Current peer-to-peer lookup algorithms have been designed with the assumption that routing information at each member node must be kept small, so that the bookkeeping required to respond to system...
Scheduling and Simulation: How to Upgrade Distributed Systems (2003)
Sameer Ajmani, Barbara Liskov, Liuba Shrira
Upgrading the software of long-lived distributed systems is difficult. It is not possible to upgrade all the nodes in a system at once, since some nodes may be down and halting the system for an...
Ownership Types for Object Encapsulation (2003)
Chandrasekhar Boyapati, Barbara Liskov, Liuba Shrira
Ownership types provide a statically enforceable way of specifying object encapsulation and enable local reasoning about program correctness in object-oriented languages. However, a type system that...
Replication in the Harp File System (2002)
Barbara Liskov, Sanjay Ghemawat, Robert Gruber, Paul Johnson, Liuba Shrira, Michael Williams
technique [1, 26, 27]. In this method, client calls are directed to a single primary server, which communicates This paper describes the design and implementation of the with other backup servers and...
Ownership Types and Safe Lazy Upgrades in Object-Oriented Databases (2002)
Rasekhar Boyapati, Barbara Liskov, Liuba Shrira
This paper describes a novel mechanism for upgrading objects in an object-oriented database. Unlike earlier systems, our mechanism is expressive, supporting a rich set of upgrades; it is ecient and...
Ownership Types and Safe Lazy Upgrades in Object-Oriented Databases (2002)
Rasekhar Boyapati, Barbara Liskov, Liuba Shrira
This paper describes a novel mechanism for upgrading objects in an object-oriented database. Unlike earlier systems, our mechanism is expressive, supporting a rich set of upgrades; it is ecient and...
Providing Persistent Objects in Distributed Systems (2002)
Barbara Liskov, Miguel Castro, Liuba Shrira, Atul Adya
THOR is a persistent object store that provides a powerful programming model. THOR ensures that persistent objects are accessed only by calling their methods and it supports atomic transactions. The...
Ownership Types and Safe Lazy Upgrades in Object-Oriented Databases (2002)
Rasekhar Boyapati, Barbara Liskov, Liuba Shrira
This paper describes a novel mechanism for upgrading objects in an object-oriented database. Unlike earlier systems, our mechanism is expressive, supporting a rich set of upgrades; it is efficient...
Ownership Types and Safe Lazy Upgrades in Object-Oriented Databases (2002)
Rasekhar Boyapati, Barbara Liskov, Liuba Shrira
This paper describes a novel mechanism for upgrading objects in an object-oriented database. Unlike earlier systems, our mechanism is expressive, supporting a rich set of upgrades; it is efficient...
Ownership Types and Safe Lazy Upgrades in Object-Oriented Databases (2002)
Rasekhar Boyapati, Barbara Liskov, Liuba Shrira
This paper describes a novel mechanism for upgrading objects in an object-oriented database. Unlike earlier systems, our mechanism is expressive, supporting a rich set of upgrades; it is ecient and...
Appears as Technical Memo MIT/LCS/TM-589, MIT Laboratory for Computer Science, June 1999 (2002)
We have developed a practical state-machine replication algorithm that tolerates Byzantine faults: it works correctly in asynchronous systems like the Internet and it incorporates several...
File Systems With Multiple File Implementations (2002)
Barbara Liskov, John Wilkes, Arthur C. Smith, Raymie Stata
This thesis proposes ideas for designing #le system software for large, high-performance #le server hardware we feel will be common in the middle to late nineties. In particular, the thesis examines...
Partitioned Garbage Collection of a Large Object Store (2002)
Umesh Maheshwari, Barbara Liskov
This paper describes a new garbage collection scheme for large persistent object stores that makes efficient use of the disk and main memory. The heap is divided into partitions that are collected...
The idea of a data abstraction has had a significant impact on the development of programming languages and on programming methodology. CLU was the first implemented programming language to provide...
A Trusted Third-Party Computation Service (2002)
Sameer Ajmani, Robert Morris, Barbara Liskov
We present TEP, a system that supports general-purpose shared computation between mutually-distrusting parties. TEP is useful for applications, such as auctions and tax preparation, that use private...
Safe Lazy Software Upgrades in Object-Oriented Databases (2002)
Barbara Liskov, Chuang-hue Moh, Steven Richman, Liuba Shrira, Yin Cheung, Rasekhar Boyapati
Object-oriented databases allow objects that are manipulated by programs to be stored reliably so that they can be used again later and shared with other programs. Since objects in the OODB may live...
The Design of a Robust Peer-to-Peer System (2002)
Rodrigo Rodrigues, Barbara Liskov, Liuba Shrira
Peer-to-peer (P2P) overlay networks have recently become one of the hottest topics in OS research. These networks bring with them the promise of harnessing idle storage and network resources from...
The Design of a Robust Peer-to-Peer System (2002)
Rodrigo Rodrigues, Barbara Liskov, Liuba Shrira
Peer-to-peer (P2P) overlay networks have recently become one of the hottest topics in OS research. These networks bring with them the promise of harnessing idle storage and network resources from...
Safe Lazy Software Upgrades in Object-Oriented Databases (2002)
Barbara Liskov, Chuang-hue Moh, Steven Richman, Liuba Shrira, Yin Cheung, Rasekhar Boyapati
Object-oriented databases allow objects that are manipulated by programs to be stored reliably so that they can be used again later and shared with other programs. Since objects in the OODB may live...
Safe Lazy Software Upgrades in Object-Oriented (2002)
Barbara Liskov, Chuang-hue Moh, Steven Richman, Liuba Shrira, Yin Cheung, Rasekhar Boyapati
Object-oriented databases allow objects that are manipulated by programs to be stored reliably so that they can be used again later and shared with other programs. Since objects in the OODB may live...
A Trusted Third-Party Computation Service (2002)
Sameer Ajmani, Robert Morris, Barbara Liskov
We present TEP, a system that supports general-purpose shared computation between mutually-distrusting parties. TEP is useful for applications, such as auctions and tax preparation, that use private...
A Trusted Third-Party Computation Service (2002)
Sameer Ajmani, Robert Morris, Barbara Liskov
We present TEP, a system that supports general-purpose shared computation between mutually-distrusting parties. TEP is useful for applications, such as auctions and tax preparation, that use private...
Approaches to Solving the Software Problem: Software Engineering and Automatic Programming. (2002)
Hammer,Michael, Liskov,Barbara
This document provides a broad thematic overview of proposed approaches to solving the software problem.
Distributed Computer Systems: Structure and Semantics, (2002)
Svobodova,Liba, Liskov,Barbara, Clark,David
This report describes an ongoing project in the area of design of distributed systems. The goal is to develop an effective programming system that will support well-structured design, implementation,...
Fast Object Operations in a Persistent Programming System (2001)
Barbara Liskov, Frederic R. Morgenthaler, Andrew C. Myers
Object-oriented, persistent programming languages offer a simple model for the programmer to write applications that share data, even among heterogeneous systems. However, poor performance limits...
Combining Abstraction with Byzantine Fault-Tolerance (2001)
Barbara Liskov, Arthur C. Smith, Rodrigo Seromenho, Miragaia Rodrigues
This thesis describes a technique to build replicated services that combines Byzantine fault tolerance with work on abstract data types. Tolerating Byzantine faults is important because software...
Using Abstraction To Improve Fault Tolerance (2001)
Miguel Castro, Rodrigo Rodrigues, Barbara Liskov
Software errors are a major cause of outages and they are increasingly exploited in malicious attacks. Byzantine fault tolerance allows replicated systems to mask some software errors but it is...
This thesis describes a technique to build replicated services that combines Byzantine fault tolerance with work on abstract data types. Tolerating Byzantine faults is important because software...
Using Abstraction To Improve Fault Tolerance (2001)
Miguel Castro, Rodrigo Rodrigues, Barbara Liskov
Software errors are a major cause of outages and they are increasingly exploited in malicious attacks. Byzantine fault tolerance allows replicated systems to mask some software errors but it is...
BASE: Using Abstraction to Improve Fault Tolerance (2001)
Rodrigo Rodrigues, Miguel Castro, Barbara Liskov
increasingly exploited in malicious attacks. Byzantine fault tolerance allows replicated systems to mask some software errors but it is expensive to deploy. This paper describes a replication...
BASE: Using Abstraction to Improve Fault Tolerance (2001)
Rodrigo Rodrigues, Miguel Castro, Barbara Liskov
Software errors are a major cause of outages and they are increasingly exploited in malicious attacks. Byzantine fault tolerance allows replicated systems to mask some software errors but it is...
A Correctness Proof for a Practical Byzantine-Fault-Tolerant Replication Algorithm (2001)
This paper presents a formal specification for the unoptimized version of our algorithm presented in Section 4 of [4] and proves its safety (but not its liveness.) The specification uses the I/O...
Lazy Reference Counting for Transactional Storage Systems (2001)
Miguel Castro, Atul Adya, Barbara Liskov
Hac is a novel technique for managing the client cache in a distributed, persistent object storage system. In a companion paper, we showed that it outperforms other techniques across a wide range of...
Client Cache Management in a Distributed Object Database (2001)
A distributed object database stores objects persistently at servers. Applications run on client machines, fetching objects into a client-side cache of objects. If fetching and cache management are...
Partitioned Garbage Collection of a Large Object Store (2001)
Umesh Maheshwari, Barbara Liskov
This paper describes a new garbage collection scheme for large persistent object stores that makes efficient use of the disk and main memory. The heap is divided into partitions that are collected...
Fast Object Operations in a Persistent Proogramming System (2001)
Barbara Liskov, Frederic R. Morgenthaler
Object-oriented, persistent programming languages offer a simple model for the programmer to write applications that share data, even among heterogeneous systems. However, poor performance limits...
Technology Square; Cambridge, Massachusetts 02139 (617) 253-5851 (2001)
Joseph A. Bank, Barbara Liskov, Andrew C. Myers
Java offers the real possibility that most programs can be written in a type-safe language. However, for Java to be broadly useful, it needs additional expressive power. This paper extends Java in...
A Technique for Constructing Highly-Available Services (2001)
Barbara Liskov, Liuba Shrira, Liuba Shrlra
service consists of replicas that reside at several different locations in a network. It presents its clients with a consistent view of its state, but the view may contain old information. Clients...
A Scalable Byzantine Fault Tolerant Secure Domain Name System (2001)
Barbara Liskov, Arthur C. Smith, Sarah Ahmed
The domain name system is the standard mechanism on the Internet to advertise and access important information about hosts. At its inception, DNS was not designed to be a secure protocol. The biggest...
The domain name system is the standard mechanism on the Internet to advertise and access important information about hosts. At its inception, DNS was not designed to be a secure protocol. The biggest...
Lazy Consistency Using Loosely Synchronized Clocks (2000)
This paper describes a newscheme for guaranteeing that transactions in a client/server system observe consistent state while they are running. The scheme is presented in conjunction with an...
HAC: Hybrid Adaptive Caching for Distributed Storage Systems (2000)
Miguel Castro, Atul Adya, Barbara Liskov, Andrew C. Myers
This paper presents HAC, a novel technique for managing the client cache in a distributed, persistent object storage system. HAC is a hybrid between page and object caching that combines the virtues...
Proactive Recovery in a Byzantine-Fault-Tolerant System (2000)
This paper describes an asynchronous state-machine replication system that tolerates Byzantine faults, which can be caused by malicious attacks or software errors. Our system is the first to recover...