731954
Separating agreement from execution for byzantine fault tolerant services
We describe a new architecture for Byzantine fault tolerant state machine replication that separates agreement that orders requests from execution that processes 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.
57028
Fast Byzantine Consensus
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 two-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 two-step execution despite some number t of failures (t les f). We show that this parameterized two-step consensus protocol is also optimal in terms of both number of communication steps and number of processes
53305414
Fast Byzantine Consensus
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 two-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 two-step execution despite some number t of failures (t les f). We show that this parameterized two-step consensus protocol is also optimal in terms of both number of communication steps and number of processes
7300615
Minimal Byzantine Storage
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. 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. 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.
5918485
A framework for dynamic Byzantine storage
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.
6708049
Understanding New Metaphors
Metaphors are widespread in natural language. Most natural language processing systems have failed to adequately deal with this issue. A two part approach to this problem involving a Metaphoric Lexicon and a dynamic extension system is described. The extension mechanism operates by analogically mapping previously understood mappings to account for new uses based on known regularities in the English metaphor system. A system based on this approach has been applied to the UNIX domain. Results indicate that this domain exhibits all the predicted regularities and that understanding new senses is possible using these regularities
14531338
Building a Foundation System for Producing Short Answers to Factual Questions
In this paper we describe question answering research being pursued as a joint project between Columbia University and the University of Colorado at Boulder as part of ARDA’s AQUAINT program. As a foundation for targeting complex questions involving opinions, events, and paragraph-length answers, we recently built two systems for answering short factual questions. We submitted results from the two systems to TREC’s Q&A track, and the bulk of this paper describes the methods used in building each system and the results obtained. We conclude by discussing current work aiming at combining modules from the two systems in a unified, more accurate system and adding capabilities for producing complex answers in addition to short ones.
33984452
Using System Networks to Build Rhetorical Structures
We are currently engaged in a project to study the generation of instructional texts for common consumer devices. Our initial efforts have focused on an exhaustive corpus-based analysis of instruction booklets for cordless telephones. In this paper, we present our analysis of the way the various processes used in this domain are expressed. Our emphasis here is on the relationship between the surface grammatical coding of these processes and the underlying rhetorical structure of the text. This analysis has been formalized using a systemic-functional framework, with the resulting system networks forming the basis for the Imagene text generation system.
15685117
MetaBank: A Knowledge-Base of Metaphoric Language Conventions
The frequent and conventional use of nonliteral language has been a major stumbling block for natural language processing systems since the early machine translation efforts. Metaphor, metonymy, and indirect speech acts are among the most troublesome phenomena. Recent computational efforts addressing these problems have taken an approach that emphasizes the use of systematic knowledge about nonliteral language conventions. We are currently engaged in an effort to supply this knowledge in the case of conventional metaphor. We are constructing MetaBank: an empirically derived and theoretically motivated knowledge-base of English metaphorical conventions. This article describes our three-part approach to the construction of MetaBank: the collection of on-line textual resources and databases of linguistic generalizations, the development of a methodology for analyzing these resources, and the construction of a knowledge-base based on the preceding analyses.
6534012
PreBIND and Textomy – mining the biomedical literature for protein-protein interactions using a support vector machine
BackgroundThe majority of experimentally verified molecular interaction and biological pathway data are present in the unstructured text of biomedical journal articles where they are inaccessible to computational methods. The Biomolecular interaction network database (BIND) seeks to capture these data in a machine-readable format. We hypothesized that the formidable task-size of backfilling the database could be reduced by using Support Vector Machine technology to first locate interaction information in the literature. We present an information extraction system that was designed to locate protein-protein interaction data in the literature and present these data to curators and the public for review and entry into BIND.ResultsCross-validation estimated the support vector machine's test-set precision, accuracy and recall for classifying abstracts describing interaction information was 92%, 90% and 92% respectively. We estimated that the system would be able to recall up to 60% of all non-high throughput interactions present in another yeast-protein interaction database. Finally, this system was applied to a real-world curation problem and its use was found to reduce the task duration by 70% thus saving 176 days.ConclusionsMachine learning methods are useful as tools to direct interaction and pathway database back-filling; however, this potential can only be realized if these techniques are coupled with human review and entry into a factual database such as BIND. The PreBIND system described here is available to the public at http://bind.ca. Current capabilities allow searching for human, mouse and yeast protein-interaction information.