Search

Your search keyword '"Liskov, Barbara"' showing total 357 results
Start Over Author "Liskov, Barbara"
357 results on '"Liskov, Barbara"'

3. Cross-chain Deals and Adversarial Commerce

Author

Herlihy, Maurice, Liskov, Barbara, and Shrira, Liuba

Subjects
Computer Science - Distributed, Parallel, and Cluster Computing
Abstract

Modern distributed data management systems face a new challenge: how can autonomous, mutually-distrusting parties cooperate safely and effectively? Addressing this challenge brings up questions familiar from classical distributed systems: how to combine multiple steps into a single atomic action, how to recover from failures, and how to synchronize concurrent access to data. Nevertheless, each of these issues requires rethinking when participants are autonomous and potentially adversarial. We propose the notion of a *cross-chain deal*, a new way to structure complex distributed computations that manage assets in an adversarial setting. Deals are inspired by classical atomic transactions, but are necessarily different, in important ways, to accommodate the decentralized and untrusting nature of the exchange. We describe novel safety and liveness properties, along with two alternative protocols for implementing cross-chain deals in a system of independent blockchain ledgers. One protocol, based on synchronous communication, is fully decentralized, while the other, based on semi-synchronous communication, requires a globally shared ledger., Comment: To appear in VLDB 2020

Published
2019
Full Text
View/download PDF

4. The Impact of Timestamp Granularity in Optimistic Concurrency Control

Author

Huang, Yihe, Bai, Hao, Kohler, Eddie, Liskov, Barbara, and Shrira, Liuba

Subjects
Computer Science - Databases
Abstract

Optimistic concurrency control (OCC) can exploit the strengths of parallel hardware to provide excellent performance for uncontended transactions, and is popular in high-performance in-memory databases and transactional systems. But at high contention levels, OCC is susceptible to frequent aborts, leading to wasted work and degraded performance. Contention managers, mixed optimistic/pessimistic concurrency control algorithms, and novel optimistic-inspired concurrency control algorithms, such as TicToc, aim to address this problem, but these mechanisms introduce sometimes-high overheads of their own. We show that in real-world benchmarks, traditional OCC can outperform these alternative mechanisms by simply adding fine-grained version timestamps (using different timestamps for disjoint components of each record). With fine-grained timestamps, OCC gets 1.14x TicToc's throughput in TPC-C at 128 cores (previous work reported TicToc having 1.8x higher throughput than OCC at 80 hyperthreads). Our study shows that timestamp granularity has a greater impact than previously thought on the performance of transaction processing systems, and should not be overlooked in the push for faster concurrency control schemes.

Published
2018

8. From Viewstamped Replication to Byzantine Fault Tolerance

Author

Liskov, Barbara, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Charron-Bost, Bernadette, editor, Pedone, Fernando, editor, and Schiper, André, editor

Published
2010
Full Text
View/download PDF

9. Modular Software Upgrades for Distributed Systems

Author

Ajmani, Sameer, Liskov, Barbara, Shrira, Liuba, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Thomas, Dave, editor

Published
2006
Full Text
View/download PDF

10. High Availability in DHTs: Erasure Coding vs. Replication

Author

Rodrigues, Rodrigo, Liskov, Barbara, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Castro, Miguel, editor, and van Renesse, Robbert, editor

Published
2005
Full Text
View/download PDF

14. Byzantine Clients Rendered Harmless

Author

Liskov, Barbara, Rodrigues, Rodrigo, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Fraigniaud, Pierre, editor

Published
2005
Full Text
View/download PDF

18. Argus

Author

Liskov, Barbara, Goos, G., editor, Hartmanis, J., editor, Barstow, D., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Luckham, D., editor, Moler, C., editor, Pnueli, A., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, Simons, Barbara, editor, and Spector, Alfred, editor

Published
1990
Full Text
View/download PDF

21. BASE: Using abstraction to improve fault tolerance

Author

Castro, Miguel, Rodrigues, Rodrigo, and Liskov, Barbara

Subjects
Fault tolerance, Fault tolerance (Computers) -- Research
Abstract

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 expensive to deploy. This paper describes a replication technique, BASE, which uses abstraction to reduce the cost of Byzantine fault tolerance and to improve its ability to mask software errors. BASE reduces cost because it enables reuse of off-the-shelf service implementations. It improves availability because each replica can be repaired periodically using an abstract view of the state stored by correct replicas, and because each replica can run distinct or nondeterministic service implementations, which reduces the probability of common mode failures. We built an NFS service where each replica can run a different off-the-shelf file system implementation, and an object-oriented database where the replicas ran the same, nondeterministic implementation. These examples suggest that our technique can be used in practice--in both cases, the implementation required only a modest amount of new code, and our performance results indicate that the replicated services perform comparably to the implementations that they reuse. Categories and Subject Descriptors: C.2.0 [Computer-Communication Networks]: General--Security and protection; C.2.4 [Computer-Communication Networks]: Distributed Systems--Client/server; D.4.3 [Operating Systems]: File Systems Management; D.4.5 [Operating Systems]: Reliability--Fault tolerance; D.4.6 [Operating Systems]: Security and Protection--Access controls; authentication; cryptographic controls; D.4.8 [Operating Systems]: Performance--Measurements; H.2.0 [Database Management]: General--Security, integrity, and protection; H.2.4 [Database Management]: Systems--Object-oriented databases General Terms: Security, Reliability, Algorithms, Performance, Measurement Additional Key Words and Phrases: Byzantine fault tolerance, state machine replication, proactive recovery, asynchronous systems, N-version programming

Published
2003

24. Practical Byzantine fault tolerance and proactive recovery

Author

Castro, Miguel and Liskov, Barbara

Subjects
Internet, Fault tolerance, ATM, Encryption, Data security issue, Internet -- Usage, Fault tolerance (Computers) -- Research, Computer networks -- Quality management, Information networks, Asynchronous communications -- Usage, Data encryption -- Usage, Data security -- Research
Abstract

Our growing reliance on online services accessible on the Internet demands highly available systems that provide correct service without interruptions. Software bugs, operator mistakes, and malicious attacks are a major cause of service interruptions and they can cause arbitrary behavior, that is, Byzantine faults. This article describes a new replication algorithm, BFT, that can be used to build highly available systems that tolerate Byzantine faults. BFT can be used in practice to implement real services: it performs well, it is safe in asynchronous environments such as the Internet, it incorporates mechanisms to defend against Byzantine-faulty clients, and it recovers replicas proactively. The recovery mechanism allows the algorithm to tolerate any number of faults over the lifetime of the system provided fewer than 1/3 of the replicas become faulty within a small window of vulnerability. BFT has been implemented as a generic program library with a simple interface. We used the library to implement the first Byzantine-fault-tolerant NFS file system, BFS. The BFT library and BFS perform well because the library incorporates several important optimizations, the most important of which is the use of symmetric cryptography to authenticate messages. The performance results show that BFS performs 2% faster to 24% slower than production implementations of the NFS protocol that are not replicated. This supports our claim that the BFT library can be used to build practical systems that tolerate Byzantine faults. Categories and Subject Descriptors: C.2.0 [Computer-Communication Networks]: General--Security and protection; C.2.4 [Computer-Communication Networks]: Distributed Systems--Client/server; D.4.3 [Operating Systems]: File Systems Management; D.4.5 [Operating Systems]: Reliability--Fault tolerance; D.4.6 [Operating Systems]: Security and Protection--Access controls; authentication; cryptographic controls; D.4.8 [Operating Systems]: Performance--Measurements General Terms: Security, Reliability, Algorithms, Performance, Measurement Additional Key Words and Phrases: Byzantine fault tolerance, state machine replication, proactive recovery, asynchronous systems, state transfer

Published
2002

33. Providing high availability using lazy replication

Author

Ladin, Rivka, Liskov, Barbara, Shrira, Liuba, and Ghemawat, Sanjay

Subjects
New Technique, Distributed Systems, System Design, Research and Development, Fault Tolerance, Reliability, Concurrency Control, Client/server architecture, Distributed processing (Computers) -- Research, Fault tolerance (Computers) -- Design and construction, Client/server architecture -- Research
Published
1992

34. Efficient at-most-once messages based on synchronized clocks

Author

Liskov, Barbara, Shrira, Liuba, and Wroclawski, John

Subjects
Protocol, Message Switching, Algorithm, Design, Performance, Distributed Systems, Network Architecture, Remote Procedure Call, Synchronization, Clocks, Store-and-Forward
Published
1991

37. Modular program construction using abstractions

Author

Liskov, Barbara, Goos, G., editor, Hartmanis, J., editor, Brauer, W., editor, Brinch Hansen, P., editor, Gries, D., editor, Moler, C., editor, Seegmüller, G., editor, Stoer, J., editor, Wirth, N., editor, and Bjøorner, Dines, editor

Published
1980
Full Text
View/download PDF

43. Transactional Consistency and Automatic Management in an Application Data Cache

Author

Ports, Dan R. K., Clements, Austin T., Zhang, Irene, Madden, Samuel R., Liskov, Barbara H., Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Madden, Samuel R., Ports, Dan R. K., Clements, Austin T., Zhang, Irene, and Liskov, Barbara H.

Subjects
GeneralLiterature_REFERENCE(e.g.,dictionaries,encyclopedias,glossaries), GeneralLiterature_MISCELLANEOUS, ComputingMilieux_MISCELLANEOUS
Abstract

http://www.usenix.org/events/osdi10/tech/techAbstracts.html#Ports, Distributed in-memory application data caches like memcached are a popular solution for scaling database-driven web sites. These systems are easy to add to existing deployments, and increase performance significantly by reducing load on both the database and application servers. Unfortunately, such caches do not integrate well with the database or the application. They cannot maintain transactional consistency across the entire system, violating the isolation properties of the underlying database. They leave the application responsible for locating data in the cache and keeping it up to date, a frequent source of application complexity and programming errors. Addressing both of these problems, we introduce a transactional cache, TxCache, with a simple programming model. TxCache ensures that any data seen within a transaction, whether it comes from the cache or the database, reflects a slightly stale but consistent snapshot of the database. TxCache makes it easy to add caching to an application by simply designating functions as cacheable; it automatically caches their results, and invalidates the cached data as the underlying database changes. Our experiments found that adding TxCache increased the throughput of a web application by up to 5.2×, only slightly less than a non-transactional cache, showing that consistency does not have to come at the price of performance.

Published
2010

44. Census: Location-Aware Membership Management for Large-Scale Distributed Systems

Author

Cowling, James Alexander, Ports, Dan R. K., Liskov, Barbara H., Popa, Raluca Ada, Gaikwad, Abhijeet, Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Liskov, Barbara H., Cowling, James Alexander, Ports, Dan R. K., and Popa, Raluca Ada

Abstract

We present Census, a platform for building large-scale distributed applications. Census provides a membership service and a multicast mechanism. The membership service provides every node with a consistent view of the system membership, which may be global or partitioned into location-based regions. Census distributes membership updates with low overhead, propagates changes promptly, and is resilient to both crashes and Byzantine failures. We believe that Census is the first system to provide a consistent membership abstraction at very large scale, greatly simplifying the design of applications built atop large deployments such as multi-site data centers. Census builds on a novel multicast mechanism that is closely integrated with the membership service. It organizes nodes into a reliable overlay composed of multiple distribution trees, using network coordinates to minimize latency. Unlike other multicast systems, it avoids the cost of using distributed algorithms to construct and maintain trees. Instead, each node independently produces the same trees from the consistent membership view. Census uses this multicast mechanism to distribute membership updates, along with application-provided messages. We evaluate the platform under simulation and on a real-world deployment on PlanetLab. We find that it imposes minimal bandwidth overhead, is able to react quickly to node failures and changes in the system membership, and can scale to substantial size., National Science Foundation (U.S.) (ITR grant CNS-0428107)

Published
2009

50. DISTRIBUTED PROGRAMMING IN ARGUS.

Author

Liskov, Barbara

Subjects
*PROGRAMMING languages, *COMPUTER systems
Abstract

Provides information on Argus, a programming language and system developed to support the implementation and execution of distributed programs. Provision of mechanisms that help programmers cope with the special problems that arise in distributed programs, such as network partitions and crashes of remote nodes.

Published
1988
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results