Search

We explore the correctness of the Certified Propagation Algorithm (CPA) [5, 1, 7, 4] in solving broadcast with locally bounded Byzantine faults. CPA allows the nodes to use only local information regarding the network topology. We provide a tight necessary and sufficient condition on the network topology for the correctness of CPA. We also present some simple extensions of this result.

For synchronous point-to-point n-node networks of undirected links, it has been previously shown that, to achieve consensus in presence of up to f Byzantine faults, the following two conditions are together necessary and sufficient.

Recent improvements in positioning technology make massive moving object data widely available. One important analysis is to find the moving objects that travel together. Existing methods put a strong constraint in defining moving object cluster, that they require the moving objects to stick together for consecutive timestamps. Our key observation is that the moving objects in a cluster may actually diverge temporarily and congregate at certain timestamps. Motivated by this, we propose the concept of swarm which captures the moving objects that move within arbitrary shape of clusters for certain timestamps that are possibly nonconsecutive. The goal of our paper is to find all discriminative swarms, namely closed swarm. While the search space for closed swarms is prohibitively huge, we design a method, ObjectGrowth, to efficiently retrieve the answer. In ObjectGrowth, two effective pruning strategies are proposed to greatly reduce the search space and a novel closure checking rule is developed to report closed swarms on-the-fly. Empirical studies on the real data as well as large synthetic data demonstrate the effectiveness and efficiency of our methods., Presented at The 36th International Conference on Very Large Data Bases, September 13-17, 2010, Singapore. Sponsored in party ARL.

In this article, we describe a novel, general-purpose multicore architecture-the Bulk Multicore-we designed to enable a highly programmable environment. In it, the programmer and runtime system are relieved of having to manage the sharing of data thanks to novel support for scalable hardware cache coherence. Moreover, to help minimize the chance of parallel-programming errors, the Bulk Multicore provides to the software high-performance sequential memory consistency and also introduces several novel hardware primitives. These primitives can be used to build a sophisticated program-development-and-debugging environment, including low-overhead data-race detection, deterministic replay of parallel programs, and high-speed disambiguation of sets of addresses., Published in Communications of the ACM, v62 n12 p58-65 Dec 2009.

In this paper, we report our experiments in the TREC 2009 Million Query Track. Our first line of study is on proximity-based feedback, in which we propose a positional relevance model (PRM) to exploit term proximity evidence so as to assign more weights to expansion words that are closer to query words in feedback documents. The second line of study is to improve the weighting of feedback documents in the relevance model by using a regression-based method to approximate the probability of relevance (and thus the name RegRM). In the third line of study, we test a supervised approach for query classification. Besides, we also evaluate a selective pseudo feedback strategy which stops pseudo feedback for precision-oriented queries and only uses it for recall-oriented ones. The proposed PRM has shown clear improvements over the relevance model for pseudo feedback, suggesting that capturing the term proximity heuristic appropriately could lead to a better feedback model. RegRM performs as well as relevance model, but no noticeable improvement is observed. Unfortunately, the proposed query classification methods appear to not work well. The results also show that the proposed selective pseudo feedback may not work well, since precision-oriented queries can also benefit from pseudo feedback, though not as much as recall-oriented queries., Proceedings of the Eighteenth Text REtrieval Conference (TREC 2009) held in Gaithersburg, Maryland, November 17-20, 2009. The conference was co-sponsored by the National Institute of Standards and Technology (NIST) the Defense Advanced Research Projects Agency (DARPA) and the Advanced Research and Development Activity (ARDA).

In this paper, we report our experiments in the TREC 2008 Relevance Feedback Track. Our main goal is to study a novel problem in feedback, i.e., optimization of the balance of the query and feedback information. Intuitively, if we over-trust the feedback information, we may be biased to favor a particular subset of relevant documents, but under-trusting it would not take advantage of feedback. In the current feedback methods, the balance is usually controlled by some parameter, which is often set to a fixed value across all the queries and collections. However, due to the difference in queries and feedback documents, this balance parameter should be optimized for each query and each set of feedback documents. To address this problem, we present a learning approach to adaptively predict the balance coefficient (i.e., feedback coefficient). First, three heuristics are proposed to characterize the relationships between feedback coefficient and other measures, including discrimination of query, discrimination of feedback documents, and divergence between the query and the feedback documents. Then, taking these three heuristics as a road map, we explore a number of features and combine them using a logistic regression model to predict the feedback coefficient. Experiments show that our adaptive relevance feedback is more robust and effective than the regular fixed-coefficient relevance feedback., Presented at the Text REtrieval Conference (17th) (TREC 2008) held in Gaithersburg, MD on 18-21 Nov 2008. Sponsored in part by NSF Grant no. FIBR-0425852.

The availability of multiple orthogonal channels in a wireless network can potentially lead to substantial performance improvement by alleviating contention and interference. However, this also gives rise to non-trivial channel coordination issues. The situation is exacerbated by variability in the achievable data-rates across channels and links. Thus, scheduling in such networks may require substantial information-exchange and lead to non-negligible overhead. This provides a strong motivation for the study of scheduling algorithms that can operate with limited information, while still providing acceptable worst-case performance guarantees. In this paper, we make an effort in this direction, by examining the scheduling implications of multiple channels, and heterogeneity in channel-rates. We establish lower bounds on performance of a class of maximal schedulers, and describe a scheduler that require limited information-exchange between nodes. We first demonstrate that when the underlying scheduling mechanism is "imperfect", the presence of multiple orthogonal channels can help alleviate the detrimental impact of the imperfect scheduler, and yield a significantly better efficiency-ratio in a wide range of network topologies. We then establish performance bounds for a scheduler than can achieve good efficiency-ratios in the presence of channels with heterogeneous rates without requiring explicit exchange of queue-information. Our results indicate that it may be possible to achieve a desirable trade-off between performance and information., Supported in part by NSF.

ion reduces the problem of whether an infinite state system satisfies a temporal logic property to model checking that property on a finite state abstract version. The most common abstractions are quotients of the original system. We present a simple method of defining quotient abstractions by means of equations collapsing the set of states. Our method yields the minimal quotient system together with a set of proof obligations that guarantee its executability and can be discharged with tools such as those in the Maude formal environment., Sponsored in part by DARPA and AFRL.

We argued for the need to study the performance of multi-channel networks in situations where there are constraints on channel switching. We proposed some constraint models in [1] to capture some expected constraints, and analyzed two such models, viz., adjacent (c,f) assignment and random (c,f) assignment. We studied the impact of such restricted switching, quantified by the parameter f (where f is the number of channels an individual node may switch to) in the regime c = O(log n). One of our proposed models was termed random (c,f) assignment.

This paper argues for the need to address the issue of multi-channel network performance under constraints on channel switching. We present examples from emergent directions in wireless networking to motivate the need for such a study, and introduce some models to capture channel switching constraints. For some of these models, we study connectivity and capacity of a wireless network comprising n randomly deployed nodes, equipped with a single interface each, when there are c = O(log n) channels of equal bandwidth w/c available. We consider an adjacent (c,f) channel assignment where a node may switch between f adjacent channels, but the adjacent channel block is randomly assigned., Extended version of Infocom 2007 Paper. Supported in part by NSF.

Global computing involves the interplay of a vast variety of languages, but practially useful foundations for language specification and prototyping at the semantic level are lacking. In this paper we present a systematic approach consisting of three techniques: (1) A generic calculus of explicit substitutions with names (called CINNI) that allows us to give a first-order representation of syntax to uniformly deal with all binding aspects. (2) An executable representation of Felleisen-style operational semantics in terms of first-order rewrite rules. (3) A logical framework, namely rewriting logic, that allows us to express (1) and (2) and, in addition, language aspects such as concurrency and non-determinism. We illustrate the use of these techniques in two applications: (1) A formal specification and analysis of PLAN, a Packet Language for Active Networks, that has been developed in the Switchware project at UPenn. This work was conducted in the scope of the DARPA Active Network Program. (2) The development of CIAO, a Calculus of Imperative Active Objects, a core language for concurrent object-oriented programming. It is especially designed to allow the representation of practically relevant sublanguages of common object-oriented languages such as Java, C#, and C++. This second application is subject of ongoing work., Supported in part by AFRL, NSF under contract CCR-9900334 and ONR under contract N00012-99-C-0198 and N00014-02-1-0715.

An automated and configurable technique for runtime safety analysis of multithreaded programs is presented, which is able to predict safety violations from successful executions. Based on a user provided safety formal specification, the program is automatically instrumented to emit relevant state update events to an observer, which further checks them against the safety specification. The events are stamped with dynamic vector clocks, enabling the observer to infer a causal partial order on the state updates. All event traces that are consistent with this partial order, including the actual execution trace, are analyzed on-line and in parallel, and a warning is issued whenever there is a trace violating the specification. This technique can be therefore seen as a bridge between testing and model checking. To further increase scalability, a window in the state space can be specified, allowing the observer to infer the most probable runs. If the size of the window is 1 then only the received execution trace is analyzed, like in testing; if the size of the window is then all the execution traces are analyzed, such as in model checking., Sponsored in part by ONR Grant No. N00014-02-1-0715 and by NSF/NASA Joint Grant No. CCR-0234524.

In unit testing, a program is decomposed into units which are collections of functions. A part of unit can be tested by generating inputs for a single entry function. The entry function may contain pointer arguments, in which case the inputs to the unit are memory graphs. The paper addresses the problem of automating unit testing with memory graphs as inputs. The approach used builds on previous work combining symbolic and concrete execution, and more specifically, using such a combination to generate test inputs to explore all feasible execution paths. The current work develops a method to represent and track constraints that capture the behavior of a symbolic execution of a unit with memory graphs as inputs. Moreover, an efficient constraint solver is proposed to facilitate incremental generation of such test inputs. Finally, CUTE, a tool implementing the method is described together with the results of applying CUTE to real-world examples of C code.

Cross-Layer for Data Accessibility: Scenario- Mobile users create multimedia data and share them with others. Problems- Users should learn about each other's data and its location; Network can become partitioned, which leads to missing data; We need middleware services and routing services to collaborate for effective data accessibility., Presented at the NATO Workshop on Cross-Layer Issues in the Design of Tactical Mobile Ad Hoc Wireless Networks, held at Naval Research Lab, Washington, DC on 2-3 June 2004. See also ADM002082, RTO-TR-IST-030, Information Management over Disadvantaged Grids. The original document contains color images. Sponsored in part by the National Science Foundation.

A process which computes the physical locations of nodes in a wireless sensor network is called localization. Self-localization is critical for large-scale sensor networks because manual or assisted localization is often impractical due to time requirements, economic constraints or inherent limitations of deployment scenarios. We have developed a service for reliably localizing wireless sensor networks in environments conducive to ranging errors by using a custom hardware-software solution for acoustic ranging and a family of self-localization algorithms. The ranging solution improves on previous work, extending the practical measurement range threefold "20-30m" while maintaining a distance-invariant median measurement error of about 1% of maximum range "33cm". The localization scheme is based on least squares scaling with soft constraints. Evaluation using ranging results obtained from sensor network field experiments shows that the localization scheme is resilient against large-magnitude ranging errors and sparse range measurements, both of which are common in large-scale outdoor sensor network deployments.

We present a system submitted to the CoNLL-2004 shared task for semantic role labeling. The system is composed of a set of classifiers and an inference procedure used both to clean the classification results and to ensure structural integrity of the final role labeling. Linguistic information is used to generate features during classification and constraints for the inference process. Semantic role labeling is a complex task to discover patterns within sentences corresponding to semantic meaning. We believe it is hopeless to expect high levels of performance from either purely manual classifiers or purely learned classifiers. Rather, supplemental linguistic information must be used to support and correct a learning system. The system we present here is composed of two phases., Supported in part by grants NSF-IIS-9984168 and NSF-EIA-0224453.

We present a system for the semantic role labeling task. The system combines a machine learning technique with an inference procedure based on integer linear programming that supports the incorporation of linguistic and structural constraints into the decision process. The system is tested on the data provided in CoNLL-2004 shared task on semantic role labeling and achieves very competitive results.

Given a collection of discrete random variables representing outcomes of learned local predictors in natural language. e.g.. named entities and relations. we seek an optimal global assignment to the variables in the presence of general (non-sequential) constraints. Examples of these constraints include the type of arguments a relation can take, and the mutual activity of different relations. etc. We develop a linear programing formulation for this problem and evaluate it in the context of simultaneously learning named entities and relations. Our approach allows us to efficiently incorporate domain and task specific constraints at decision time, resulting in significant improvements in the accuracy and the "human-like" quality of the inferences.

This paper presents a novel approach to representing 2-dimensional shapes that adaptively models different portions of the shape at different resolutions, having higher resolution where it improves the quality of the representation and lower resolution elsewhere. The proposed representation is invariant to scale, translation, and rotation. The representation is amenable to indexing using existing multidimensional index structures and can thus support efficient similarity retrieval. The experiments reported here show that the adaptive resolution technique performs significantly better compared to the fixed resolution approach previously proposed in the literature., Prepared in cooperation with the Department of Information and Computer Science, University of California at Irvine, Irvine, CA. Sponsored in part by the National Science Foundation under Grant No. IIS-9734300 and the NSF/DARPA/NASA Digital Library Initiative Program under Cooperative Agreement No. 94-11318.

The importance of multidimensional index structures to numerous emerging database applications is well established. However, before these index structures can be supported as access methods (AMs) in a commercial-strength database management system (DBMS), efficient techniques to provide transactional access to data via the index structure must be developed. Concurrent accesses to data via index structures introduce the problem of protecting ranges specified in the retrieval from phantom insertions and deletions (the phantom problem). This paper presents a dynamic granular locking approach to phantom protection in Generalized Search Trees (GiSTs), an index structure supporting an extensible set of queries and data types. The granular locking technique offers a high degree of concurrency and has a low lock overhead. Our experiments show that the granular locking technique (1) scales well under various system loads and (2) similar to the B-tree case, provides a significantly more efficient implementation compared to predicate locking for multidimensional AMs as well. Since a wide variety of multidimensional index structures can be implemented using GiST, the developed algorithms provide a general solution to concurrency control in multidimensional AMs. To the best of our knowledge, this paper provides the first such solution based on granular locking.

The causal ordering procedure of Iwasaki and Simon [5,6] provides a means for uncovering causal dependencies among variables constrained by a set of mathematical equations. This paper examines the procedure from a qualitative modeling viewpoint and addresses one of its limitations: context sensitivity. Causal dependencies predicted by the procedure may change depending on the context or scenario in which the underlying physical system operates. This prevents the qualitative modeler from using causal ordering to determine, a priori, a single causal interpretation of equations describing some phenomenon. We show that in some cases it is possible to find clusters of equations that possess causal stability. That is, their causal dependencies are the same in all scenarios consistent with the equations' modeling viewpoint. These unidirectional equations help the qualitative modeler by providing a stable, unambiguous causal interpretation. To identify such equations we define conditions sufficient to guarantee causal stability. In addition, we show that unidirectional equation sets are causally independent of equations outside their set. Thus, they add compositionality to the causal modeling task. Lastly, we demonstrate our ideas by uncovering the causal dependencies of Hooke's law, Gauss's law for electricity, and Bernoulli's equation.

In order for a program to interact with the world as well as people do, we must provide it with a great deal of commonsense about the way things work. Reasoning about the geometric interactions and motions of objects is an important part of that commonsense. Some of the most complex problems we solve involve reasoning about mechanical devices, such as gears, cams, and docks. Qualitative mechanics is the symbolic analysis of the motions and the geometric interactions of physical objects. This thesis describes a theory for analysis of rigid body mechanisms, an important subset of qualitative mechanics problems. This theory has been implemented and tested on several mechanisms including a mechanical clock. Beginning with drawings of the parts involved we compute a discrete symbolic description showing changes in position and motion of the parts of the mechanism as well as its global behavior.

Computational techniques were studied for the estimation of global discretization error in numerical solutions of both smooth and nonsmooth differential equations with an emphasis on the deferred correction technique. Of special interest were hyperbolic problems, for which mixed results were obtained. The implications of a stronger stability concept for Gaussian elimination were explored with respect to scaling, iterative refinement, and equilibration. Interesting equivalence and stability results were obtained for multistep methods for solving ordinary differential equations. (Author)

This thesis is concerned with the use of multi-level methods to solve the linear systems arising from finite element discretizations of elliptic equations. In all, three multi-level methods are considered. The first of these is applicable only to quasi-uniform grids, but is simpler than other algorithms considered in previous theoretical work. The other two algorithms are applicable to both quasi-uniform grids, and locally refined grids, those grids on which the size of the largest and smallest elements many differ by an arbitrarily large factor. All three algorithms are asymptotically optimal, producing good solutions in O(N) operations on a finite element grid with N elements. These asymptotically optimal complexity bounds for the last two algorithms are the first such bounds for multi-level methods on locally refined grids. One of these algorithms achieves this O(N) complexity bound under weaker than expected conditions on the dimensions of the finite element spaces used by the algorithm.

This report describes both a quasi-analog and a purely digital fashion of performing arithmetic using bursts. On the way the use of non-compacted bursts and the corresponding encoders is brought up. Then the general area of digital filters, realized in burst technology, is discussed and practical examples from the area of convolution, adaptive filtering and RF tuning and demodulation are given. Finally applications to picture processing and 'spatial' versions of burst processing are mentioned and suggestions made for future areas of study.

For uniform meshes it is shown that any linear k-step formula can be formulated so that only k values need to be saved between steps. By saving an additional m values it is possible to construct local polynomial approximations of degree k+m-1, which can be used as predictor formulas. Different polynomial bases lead to different equivalent forms of multistep formulas. In particular, local monomial bases yield Nordsieck formulas. An explicit one-to-one correspondence is established between Nordsieck formulas and k-step-formulas of order at least k, and a strong equivalence result is proved for all but certain pathological cases. Equivalence is also shown for P(EC)* formulas but not for P(EC)*E formulas. (Author)

BURSTLOCK is a digital phase-locked loop implemented using Burst Processing. It is used in a receiver perform FM demodulation of commercial broadcast signals. It is also shown that BURSTLOCK has some theoretical advantages over conventional phase-locked loops. (Author)

WALSHSTORE is concerned with the investigation into the application of orthogonal transforms, e.g., Walsh transforms, to the storage of visual images in a fail-soft manner, i.e., the system can sustain losses but the retrieved image can still be recognized, even if in a degraded form. The application of Burst Processing to various parts in such a system is investigated together with an analysis of the amount of storage and speed of computation that can be achieved. This paper presents the necessary theory and the implementation of the Walsh transformers and the fail-soft storage which were constructed and tested. Additionally, some software simulation results are compared to the actual machine performance. (Author)

The Block Sum Register (BSR) is a basic building block used in Burst Processing. The main difficulty with it has been the large number of discrete components required for the current sources. The paper introduces various BSR designs with considerably smaller numbers of discrete components using the electrical characteristics of the BSR's shift register. The best design is then used in an arithmetic unit which performs the basic arithmetic operations, i.e., addition, subtraction, multiplication and division. (Author)

A family of Processors has been developed to perform arithmetic on data in the Burst Format. The common building block of these circuits is a simple finite state machine called the Perverted Adder (PA) which performs BURST addition. The interconnection of PAs in a tree formation with some additional circuitry produces a Burst multiplier or divider. A PA CPU has been constructed to demonstrate these PA designs. (Author)

This paper covers the use of Burst Processing in digital filtering. Design and analysis of Burst filters is discussed in detail. A digital radio is shown as demonstration of Burst filtering. (Author)

The application of Burst Processing to the problem of spectral decomposition of speech is discussed. It is shown that such a representation provides a viable alternative to conventional speech analyzers. A specific Burst implementation is presented. (Author)

Roundoff error in the solution of linear algebraic systems is studied using a more realistic notion of what it means to perturb a problem, namely that each datum is subject to a relatively small change. The condition number is determined for this approach. A good computable error bound is given for the 'backward error'. The effect of scaling on the stability of Gaussian elimination is studied, and it is discovered that the proper way to scale a system is dependent on knowing the solution. Finally it is shown that Gaussian elimination can be stabilized by doing iterative improvement. (Author), Errata sheet inserted.

A Method for estimation of the global discretization error of solutions of operator equations is presented. Further an algorithm for iterative improvement of the approximate solution of such problems is given. The theoretical foudation for the algorithms are given as a number of theorems. Several classes of operator equations are examined and numerical results for both the error estimation algorithm and the algorithm for iterative improvement are given for some classes of ordinary and partial differential equations and integral equations. (Author)

Burst techniques are considered as possible alternatives to conventional ones in the realm of digital transmission of analog signals. Three demonstration systems using various Burst techniques are discussed in detail. (Author)

As part of the research effort investigating the properties and applications of Burst processing, the question of compatibility with the more usual weighted-binary data representations has been considered. The MICROBURST system is a microprocessor-controlled, general-purpose interface system capable of operating in a multichannel Burst environment. System structure, programming details, and support software are discussed. (Author)

In this thesis the application of Burst processing to the problem of tuning and demodulating FM signals using digital hardware was investigated. Such digital FM receivers are shown to be conceptually sound and capable of worthwhile tradeoffs of performance and economy. These results provide the basis for the implementation of a new class of digital FM receiver. The relative performance of the different configurations of the Burst receiver is discussed.

The ARC system is a double loop, damage tolerant information network. It is designed for shipboard communication among transducers, actuators, controllers, and displays. It uses hardware tests to detect damage and to effect the best reconfiguration. It can survive any one group of adjacent hits and maintain complete connectivity among the surviving nodes. (Author)

The performance of the first digital AM receiver to employ Burst techniques is discussed. Some relevant parameters are evaluated. (Author)

This paper is concerned with a control system that uses stochastic sequences as the means to reach the steady-state point. The main part of the system is a temperature transducer which outputs a stochastic sequence. The time average of the stochastic sequence is dependent upon the temperature. This sequence is then used to control a heater. A description of this system is included in this paper as well as the appropriate theory and results. A system was also constructed.

In the first part of this thesis, the architectural development of a specific machine is presented. The experiences gained during this design project indicate that there is a 'best' system architecture for a given problem. Design options become available only on lower design levels, mainly in control units. The second part of the paper analyzes the choice between microprogrammed and hardwired realizations of control units. A model which predicts the costs of equivalent microprogrammed and hardwired control units is developed. This model predicts that the cost of a hardwired control unit will increase faster than that of its microprogrammed counterpart as the control signals which must be emitted become more complex. From the same foundations, a model for the reliability of both methods can be obtained. This model predicts that the reliability of a microprogrammed control is nearly independent of the control sequence. Hardwired control units, however, suffer from decreased reliability as control complexity grows. (Author)

BURSTCALC is an arithmetic calculator which accepts inputs in Burst format and produces their sum, difference, product and quotient in Burst format, too. It uses simple counting techniques on the incoming Bursts in order to compute the desired arithmetic operation with low precision, so that relatively simple and low cost circuitry is used. However, higher precisions can be achieved by averaging the result over longer periods.

This paper describes the performance of a class of unweighted binary number representations. One of these, called burst processing, has been proposed as a compromise between stochastic and weighted-binary number representation for digital systems. Encoders, digital filters, and error correcting circuitry for these inherently redundant representations are discussed. Used as channel codes, these representations out-perform conventional error-correcting codes only in unusual circumstances. Their usefulness lies in the simplicity of the hardware required to accomplish digital signal processing tasks.