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.
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
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
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.
8865665
Evidence-based static branch prediction using machine learning
Correctly predicting the direction that branches will take is increasingly important in today's wide-issue computer architectures. The name program-based branch prediction is given to static branch prediction techniques that base their prediction on a program's structure. In this article, we investigate a new approach to program-based branch prediction that uses a body of existing programs to predict the branch behavior in a new program. We call this approach to program-based branch prediction evidence-based static prediction, or ESP. The main idea of ESP is that the behavior of a corpus of programs can be used to infer the behavior of new programs. In this article, we use neural networks and decision trees to map static features associated with each branch to a prediction that the branch will be taken. ESP shows significant advantages over other prediction mechanisms. Specifically, it is a program-based technique; it is effective across a range of programming languages and programming styles; and it does not rely on the use of expert-defined heuristics. In this article, we describe the application of ESP to the problem of static branch prediction and compare our results to existing program-based branch predictors. We also investigate the applicability of ESP across computer architectures, programming languages, compilers, and run-time systems. We provide results showing how sensitive ESP is to the number and type of static features and programs included in the ESP training sets, and we compare the efficacy of static branch prediction for subroutine libraries. Averaging over a body of 43 C and Fortran programs, ESP branch prediction results in a miss rate of 20%, as compared with the 25% miss rate obtained using the best existing program-based heuristics.
7785482
Strategies for Migration from C to Java
With the growing popularity of the Java programming language for both client and server side applications in network centric computing, there is a rising need for programming libraries that can be easily integrated into Java programs. Many mature programming libraries exist for the C programming language. This paper surveys approaches to the migration of C source code to Java and evaluates their usefulness with respect to the integration of the migrated code into Java programs.
46312706
Automatic handwriting gestures recognition using hidden Markov models
Hidden Markov models have been successfully employed in speech recognition and, more recently, in sign language interpretation. They seem adequate for visual recognition of gestures. In this paper, two problems often eluded are considered. We propose to use the Bayesian information criterion in order to determine the optimal number of model states. We describe the contribution of continuous models in opposition to symbolic ones. Experiments on handwriting gestures show recognition rate between 88% and 100%.
15290012
Shallow Semantic Parsing using Support Vector Machines
In this paper, we propose a machine learning algorithm for shallow semantic parsing, extending the work of Gildea and Jurafsky (2002), Surdeanu et al. (2003) and others. Our algorithm is based on Support Vector Machines which we show give an improvement in performance over earlier classifiers. We show performance improvements through a number of new features and measure their ability to generalize to a new test set drawn from the AQUAINT corpus.
8053050
Characterization of Neuropathological Shape Deformations
We present a framework for analyzing the shape deformation of structures within the human brain. A mathematical model is developed describing the deformation of any brain structure whose shape is affected by both gross and detailed physical processes. Using our technique, the total shape deformation is decomposed into analytic modes of variation obtained from finite element modeling, and statistical modes of variation obtained from sample data. Our method is general, and can be applied to many problems where the goal is to separate out important from unimportant shape variation across a class of objects. In this paper, we focus on the analysis of diseases that affect the shape of brain structures. Because the shape of these structures is affected not only by pathology but also by overall brain shape, disease discrimination is difficult. By modeling the brain's elastic properties, we are able to compensate for some of the nonpathological modes of shape variation. This allows us to experimentally characterize modes of variation that are indicative of disease processes. We apply our technique to magnetic resonance images of the brains of individuals with schizophrenia, Alzheimer's disease, and normal-pressure hydrocephalus, as well as to healthy volunteers. Classification results are presented.