OS Support for Portable Bulk Synchronous Parallel Programs

Predictability -- the ability to foretell that an implementation will not violate a set of specified reliability and timeliness requirements -- is a crucial, highly desirable property of responsive embedded systems. This paper overviews a development methodology for responsive systems, which enhances predictability by eliminating potential hazards resulting from physically-unsound specifications. The backbone of our methodology is the Time-constrained Reactive Automaton (TRA) formalism, which adopts a fundamental notion of space and time that restricts expressiveness in a way that allows the specification of only reactive, spontaneous, and causal computation. Using the TRA model, unrealistic systems – possessing properties such as clairvoyance, caprice, infinite capacity, or perfect timing -- cannot even be specified. We argue that this "ounce of prevention" at the specification level is likely to spare a lot of time and energy in the development cycle of responsive systems -- not to mention the elimination of potential hazards that would have gone, otherwise, unnoticed. The TRA model is presented to system developers through the Cleopatra programming language. Cleopatra features a C-like imperative syntax for the description of computation, which makes it easier to incorporate in applications already using C. It is event-driven, and thus appropriate for embedded process control applications. It is object-oriented and compositional, thus advocating modularity and reusability. Cleopatra is semantically sound; its objects can be transformed, mechanically and unambiguously, into formal TRA automata for verification purposes, which can be pursued using model-checking or theorem proving techniques. Since 1989, an ancestor of Cleopatra has been in use as a specification and simulation language for embedded time-critical robotic processes.

Systematic Verification of Safety Properties of Arbitrary Network Protocol Compositions Using CHAIN

Formal correctness of complex multi-party network protocols can be difficult to verify. While models of specific fixed compositions of agents can be checked against design constraints, protocols which lend themselves to arbitrarily many compositions of agents-such as the chaining of proxies or the peering of routers-are more difficult to verify because they represent potentially infinite state spaces and may exhibit emergent behaviors which may not materialize under particular fixed compositions. We address this challenge by developing an algebraic approach that enables us to reduce arbitrary compositions of network agents into a behaviorally-equivalent (with respect to some correctness property) compact, canonical representation, which is amenable to mechanical verification. Our approach consists of an algebra and a set of property-preserving rewrite rules for the Canonical Homomorphic Abstraction of Infinite Network protocol compositions (CHAIN). Using CHAIN, an expression over our algebra (i.e., a set of configurations of network protocol agents) can be reduced to another behaviorally-equivalent expression (i.e., a smaller set of configurations). Repeated applications of such rewrite rules produces a canonical expression which can be checked mechanically. We demonstrate our approach by characterizing deadlock-prone configurations of HTTP agents, as well as establishing useful properties of an overlay protocol for scheduling MPEG frames, and of a protocol for Web intra-cache consistency.

Automated Placement of Cameras in a Floorplan to Satisfy Task-Specific Constraints

In many multi-camera vision systems the effect of camera locations on the task-specific quality of service is ignored. Researchers in Computational Geometry have proposed elegant solutions for some sensor location problem classes. Unfortunately, these solutions utilize unrealistic assumptions about the cameras' capabilities that make these algorithms unsuitable for many real-world computer vision applications: unlimited field of view, infinite depth of field, and/or infinite servo precision and speed. In this paper, the general camera placement problem is first defined with assumptions that are more consistent with the capabilities of real-world cameras. The region to be observed by cameras may be volumetric, static or dynamic, and may include holes that are caused, for instance, by columns or furniture in a room that can occlude potential camera views. A subclass of this general problem can be formulated in terms of planar regions that are typical of building floorplans. Given a floorplan to be observed, the problem is then to efficiently compute a camera layout such that certain task-specific constraints are met. A solution to this problem is obtained via binary optimization over a discrete problem space. In preliminary experiments the performance of the resulting system is demonstrated with different real floorplans.

Automated Camera Layout to Satisfy Task-Specific and Floorplan-Specific Coverage Requirements

In many multi-camera vision systems the effect of camera locations on the task-specific quality of service is ignored. Researchers in Computational Geometry have proposed elegant solutions for some sensor location problem classes. Unfortunately, these solutions utilize unrealistic assumptions about the cameras' capabilities that make these algorithms unsuitable for many real-world computer vision applications: unlimited field of view, infinite depth of field, and/or infinite servo precision and speed. In this paper, the general camera placement problem is first defined with assumptions that are more consistent with the capabilities of real-world cameras. The region to be observed by cameras may be volumetric, static or dynamic, and may include holes that are caused, for instance, by columns or furniture in a room that can occlude potential camera views. A subclass of this general problem can be formulated in terms of planar regions that are typical of building floorplans. Given a floorplan to be observed, the problem is then to efficiently compute a camera layout such that certain task-specific constraints are met. A solution to this problem is obtained via binary optimization over a discrete problem space. In experiments the performance of the resulting system is demonstrated with different real floorplans.

Reliable Cellular Automata with Self-Organization

In a probabilistic cellular automaton in which all local transitions have positive probability, the problem of keeping a bit of information for more than a constant number of steps is nontrivial, even in an infinite automaton. Still, there is a solution in 2 dimensions, and this solution can be used to construct a simple 3-dimensional discrete-time universal fault-tolerant cellular automaton. This technique does not help much to solve the following problems: remembering a bit of information in 1 dimension; computing in dimensions lower than 3; computing in any dimension with non-synchronized transitions. Our more complex technique organizes the cells in blocks that perform a reliable simulation of a second (generalized) cellular automaton. The cells of the latter automaton are also organized in blocks, simulating even more reliably a third automaton, etc. Since all this (a possibly infinite hierarchy) is organized in "software", it must be under repair all the time from damage caused by errors. A large part of the problem is essentially self-stabilization recovering from a mess of arbitrary-size and content caused by the faults. The present paper constructs an asynchronous one-dimensional fault-tolerant cellular automaton, with the further feature of "self-organization". The latter means that unless a large amount of input information must be given, the initial configuration can be chosen to be periodical with a small period.

GENESI: Wireless sensor networks for structural monitoring

The GENESI project has the ambitious goal of bringing WSN technology to the level where it can provide the core of the next generation of systems for structural health monitoring that are long lasting, pervasive and totally distributed and autonomous. This goal requires embracing engineering and scientific challenges never successfully tackled before. Sensor nodes will be redesigned to overcome their current limitations, especially concerning energy storage and provisioning (we need devices with virtually infinite lifetime) and resilience to faults and interferences (for reliability and robustness). New software and protocols will be defined to fully take advantage of the new hardware, providing new paradigms for cross-layer interaction at all layers of the protocol stack and satisfying the requirements of a new concept of Quality of Service (QoS) that is application-driven, truly reflecting the end user perspective and expectations. The GENESI project will develop long lasting sensor nodes by combining cutting edge technologies for energy generation from the environment (energy harvesting) and green energy supply (small form factor fuel cells); GENESI will define models for energy harvesting, energy conservation in super-capacitors and supplemental energy availability through fuel cells, in addition to the design of new algorithms and protocols for dynamic allocation of sensing and communication tasks to the sensors. The project team will design communication protocols for large scale heterogeneous wireless sensor/actuator networks with energy-harvesting capabilities and define distributed mechanisms for context assessment and situation awareness. This paper presents an analysis of the GENESI system requirements in order to achieve the ambitious goals of the project. Extending from the requirements presented, the emergent system specification is discussed with respect to the selection and integration of relevant system components.The resulting integrated system will be evaluated and characterised to ensure that it is capable of satisfying the functional requirements of the project

Combining and choosing case base maintenance algorithms

Case-Based Reasoning (CBR) uses past experiences to solve new problems. The quality of the past experiences, which are stored as cases in a case base, is a big factor in the performance of a CBR system. The system's competence may be improved by adding problems to the case base after they have been solved and their solutions verified to be correct. However, from time to time, the case base may have to be refined to reduce redundancy and to get rid of any noisy cases that may have been introduced. Many case base maintenance algorithms have been developed to delete noisy and redundant cases. However, different algorithms work well in different situations and it may be difficult for a knowledge engineer to know which one is the best to use for a particular case base. In this thesis, we investigate ways to combine algorithms to produce better deletion decisions than the decisions made by individual algorithms, and ways to choose which algorithm is best for a given case base at a given time. We analyse five of the most commonly-used maintenance algorithms in detail and show how the different algorithms perform better on different datasets. This motivates us to develop a new approach: maintenance by a committee of experts (MACE). MACE allows us to combine maintenance algorithms to produce a composite algorithm which exploits the merits of each of the algorithms that it contains. By combining different algorithms in different ways we can also define algorithms that have different trade-offs between accuracy and deletion. While MACE allows us to define an infinite number of new composite algorithms, we still face the problem of choosing which algorithm to use. To make this choice, we need to be able to identify properties of a case base that are predictive of which maintenance algorithm is best. We examine a number of measures of dataset complexity for this purpose. These provide a numerical way to describe a case base at a given time. We use the numerical description to develop a meta-case-based classification system. This system uses previous experience about which maintenance algorithm was best to use for other case bases to predict which algorithm to use for a new case base. Finally, we give the knowledge engineer more control over the deletion process by creating incremental versions of the maintenance algorithms. These incremental algorithms suggest one case at a time for deletion rather than a group of cases, which allows the knowledge engineer to decide whether or not each case in turn should be deleted or kept. We also develop incremental versions of the complexity measures, allowing us to create an incremental version of our meta-case-based classification system. Since the case base changes after each deletion, the best algorithm to use may also change. The incremental system allows us to choose which algorithm is the best to use at each point in the deletion process.

Design of digital differentiators

A digital differentiator simply involves the derivation of an input signal. This work includes the presentation of first-degree and second-degree differentiators, which are designed as both infinite-impulse-response (IIR) filters and finite-impulse-response (FIR) filters. The proposed differentiators have low-pass magnitude response characteristics, thereby rejecting noise frequencies higher than the cut-off frequency. Both steady-state frequency-domain characteristics and Time-domain analyses are given for the proposed differentiators. It is shown that the proposed differentiators perform well when compared to previously proposed filters. When considering the time-domain characteristics of the differentiators, the processing of quantized signals proved especially enlightening, in terms of the filtering effects of the proposed differentiators. The coefficients of the proposed differentiators are obtained using an optimization algorithm, while the optimization objectives include magnitude and phase response. The low-pass characteristic of the proposed differentiators is achieved by minimizing the filter variance. The low-pass differentiators designed show the steep roll-off, as well as having highly accurate magnitude response in the pass-band. While having a history of over three hundred years, the design of fractional differentiator has become a ‘hot topic’ in recent decades. One challenging problem in this area is that there are many different definitions to describe the fractional model, such as the Riemann-Liouville and Caputo definitions. Through use of a feedback structure, based on the Riemann-Liouville definition. It is shown that the performance of the fractional differentiator can be improved in both the frequency-domain and time-domain. Two applications based on the proposed differentiators are described in the thesis. Specifically, the first of these involves the application of second degree differentiators in the estimation of the frequency components of a power system. The second example concerns for an image processing, edge detection application.

A mathematical theory of stochastic microlensing. II. Random images, shear, and the Kac-Rice formula

Continuing our development of a mathematical theory of stochastic microlensing, we study the random shear and expected number of random lensed images of different types. In particular, we characterize the first three leading terms in the asymptotic expression of the joint probability density function (pdf) of the random shear tensor due to point masses in the limit of an infinite number of stars. Up to this order, the pdf depends on the magnitude of the shear tensor, the optical depth, and the mean number of stars through a combination of radial position and the star's mass. As a consequence, the pdf's of the shear components are seen to converge, in the limit of an infinite number of stars, to shifted Cauchy distributions, which shows that the shear components have heavy tails in that limit. The asymptotic pdf of the shear magnitude in the limit of an infinite number of stars is also presented. All the results on the random microlensing shear are given for a general point in the lens plane. Extending to the general random distributions (not necessarily uniform) of the lenses, we employ the Kac-Rice formula and Morse theory to deduce general formulas for the expected total number of images and the expected number of saddle images. We further generalize these results by considering random sources defined on a countable compact covering of the light source plane. This is done to introduce the notion of global expected number of positive parity images due to a general lensing map. Applying the result to microlensing, we calculate the asymptotic global expected number of minimum images in the limit of an infinite number of stars, where the stars are uniformly distributed. This global expectation is bounded, while the global expected number of images and the global expected number of saddle images diverge as the order of the number of stars. © 2009 American Institute of Physics.

Exact analytical expressions for the potential of electrical double layer interactions for a sphere-plate system.

Exact, closed-form analytical expressions are presented for evaluating the potential energy of electrical double layer (EDL) interactions between a sphere and an infinite flat plate for three different types of interactions: constant potential, constant charge, and an intermediate case as given by the linear superposition approximation (LSA). By taking advantage of the simpler sphere-plate geometry, simplifying assumptions used in the original Derjaguin approximation (DA) for sphere-sphere interaction are avoided, yielding expressions that are more accurate and applicable over the full range of κa. These analytical expressions are significant improvements over the existing equations in the literature that are valid only for large κa because the new equations facilitate the modeling of EDL interactions between nanoscale particles and surfaces over a wide range of ionic strength.

The synchronization of superparamagnetic beads driven by a micro-magnetic ratchet.

We present theoretical, numerical, and experimental analyses on the non-linear dynamic behavior of superparamagnetic beads exposed to a periodic array of micro-magnets and an external rotating field. The agreement between theoretical and experimental results revealed that non-linear magnetic forcing dynamics are responsible for transitions between phase-locked orbits, sub-harmonic orbits, and closed orbits, representing different mobility regimes of colloidal beads. These results suggest that the non-linear behavior can be exploited to construct a novel colloidal separation device that can achieve effectively infinite separation resolution for different types of beads, by exploiting minor differences in their bead's properties. We also identify a unique set of initial conditions, which we denote the "devil's gate" which can be used to expeditiously identify the full range of mobility for a given bead type.

Fermion bag approach to lattice field theories

We propose a new approach to the fermion sign problem in systems where there is a coupling U such that when it is infinite the fermions are paired into bosons, and there is no fermion permutation sign to worry about. We argue that as U becomes finite, fermions are liberated but are naturally confined to regions which we refer to as fermion bags. The fermion sign problem is then confined to these bags and may be solved using the determinantal trick. In the parameter regime where the fermion bags are small and their typical size does not grow with the system size, construction of Monte Carlo methods that are far more efficient than conventional algorithms should be possible. In the region where the fermion bags grow with system size, the fermion bag approach continues to provide an alternative approach to the problem but may lose its main advantage in terms of efficiency. The fermion bag approach also provides new insights and solutions to sign problems. A natural solution to the "silver blaze problem" also emerges. Using the three-dimensional massless lattice Thirring model as an example, we introduce the fermion bag approach and demonstrate some of these features. We compute the critical exponents at the quantum phase transition and find ν=0.87(2) and η=0.62(2). © 2010 The American Physical Society.

Scaling limits of a model for selection at two scales

The dynamics of a population undergoing selection is a central topic in evolutionary biology. This question is particularly intriguing in the case where selective forces act in opposing directions at two population scales. For example, a fast-replicating virus strain outcompetes slower-replicating strains at the within-host scale. However, if the fast-replicating strain causes host morbidity and is less frequently transmitted, it can be outcompeted by slower-replicating strains at the between-host scale. Here we consider a stochastic ball-and-urn process which models this type of phenomenon. We prove the weak convergence of this process under two natural scalings. The first scaling leads to a deterministic nonlinear integro-partial differential equation on the interval $[0,1]$ with dependence on a single parameter, $\lambda$. We show that the fixed points of this differential equation are Beta distributions and that their stability depends on $\lambda$ and the behavior of the initial data around $1$. The second scaling leads to a measure-valued Fleming-Viot process, an infinite dimensional stochastic process that is frequently associated with a population genetics.

Cannibal Animal Games: A new variant of Tic-Tac-Toe

This paper presents a new partial two-player game, called the cannibal animal game, which is a variant of Tic-Tac-Toe. The game is played on the infinite grid, where in each round a player chooses and occupies free cells. The first player Alice can occupy a cell in each turn and wins if she occupies a set of cells, the union of a subset of which is a translated, reflected and/or rotated copy of a previously agreed upon polyomino P (called an animal). The objective of the second player Bob is to prevent Alice from creating her animal by occupying in each round a translated, reflected and/or rotated copy of P. An animal is a cannibal if Bob has a winning strategy, and a non-cannibal otherwise. This paper presents some new tools, such as the bounding strategy and the punching lemma, to classify animals into cannibals or non-cannibals. We also show that the pairing strategy works for this problem.

A new inversion procedure for confocal scanning microscopy and other bandlimited signal processing problems

We find a simple analytic expression for the inverse of an infinite matrix related to the problem of data reduction in confocal scanning microscopy and other band-limited signal processing problems. Potential applications of this result to practical problems are outlined. The matrix arises from a sampling expansion approach to the integral equation.