A criterion for atomicity revisited

Concurrent and reactive programs are specified by their behaviours in the presence of a nondeterministic environment. In a natural way, this gives a specification (ARW) of an atomic variable in the style of Abadi and Lamport. Several implementations of atomic variables by lower level primitives are known. A few years ago, we formulated a criterion to prove the correctness of such implementations. The proof of correctness of the criterion itself was based on Lynch’s definition of atomicity by serialization points. Here, this criterion is reformulated as a specification HRW in the formal sense. Simulations from HRW to ARW and vice versa are constructed. These now serve as a constructive proof of correctness of the criterion. Eternity variables are used in the simulation from HRW to ARW. We propose so-called gliding simulations to deal with the problems that appear when occasionally the concrete implementation needs fewer steps than the abstract specification.     

A queue based mutual exclusion algorithm

A new elegant and simple algorithm for mutual exclusion of N processes is proposed. It only requires shared variables in a memory model where shared variables need not be accessed atomically. We prove mutual exclusion by reformulating the algorithm as a transition system (automaton), and applying simulation of automata. The proof has been verified with the higher-order interactive theorem prover PVS. Under an additional atomicity assumption, the algorithm is starvation free, and we conjecture that no competing process is passed by any other process more than once. This conjecture was verified by model checking for systems with at most five processes.     

Nonatomic dual bakery algorithm with bounded tokens

A simple mutual exclusion algorithm is presented that only uses nonatomic shared variables of bounded size, and that satisfies bounded overtaking. When the shared variables behave atomically, it has the first-come-first-served property (FCFS). Nonatomic access makes information vulnerable. The effects of this can be mitigated by minimizing the information and by spreading it over more variables. The design approach adopted here begins with such mitigating efforts. These resulted in an algorithm with a proof of correctness, first for atomic variables. This proof is then used as a blueprint for the simultaneous development of the algorithm for nonatomic variables and its proof. Mutual exclusion is proved by means of invariants. Bounded overtaking and liveness under weak fairness are proved with invariants and variant functions. Liveness under weak fairness is formalized and proved in a set-theoretic version of temporal logic. All these assertions are verified with the proof assistant PVS. We heavily rely on the possibility offered by a proof assistant like PVS to reuse proofs developed for one context in a different context.     

Homogenization-based multiscale crack modelling: From micro-diffusive damage to macro-cracks

The existence of a representative volume element (RVE) for a class of quasi-brittle materials having a random heterogeneous microstructure in tensile, shear and mixed mode loading is demonstrated by deriving traction–separation relations, which are objective with respect to RVE size. A computational homogenization based multiscale crack modelling framework, implemented in an FE² setting, for quasi-brittle solids with complex random microstructure is presented. The objectivity of the macroscopic response to the micro-sample size is shown by numerical simulations. Therefore, a homogenization scheme, which is objective with respect to macroscopic discretization and microscopic sample size, is devised. Numerical examples including a comparison with direct numerical simulation are given to demonstrate the performance of the proposed method.     

Formalizing a hierarchical file system

An abstract file system is defined here as a partial function from (absolute) paths to data. Such a file system determines the set of valid paths. It allows the file system to be read and written at a valid path, and it allows the system to be modified by the Unix operations for creation, removal, and moving of files and directories. We present abstract definitions (axioms) for these operations. This specification is refined towards a pointer implementation. The challenge is to have a natural abstraction function from the implementation to the specification, to define operations on the concrete store that behave exactly in the same way as the corresponding functions on the abstract store, and to prove these facts. To mitigate the problems attached to partial functions, we do this in two steps: first a refinement towards a pointer implementation with total functions, followed by one that allows partial functions. These two refinements are proved correct by means of a number of invariants. Indeed, the insights gained consist, on the one hand, of the invariants of the pointer implementation that are needed for the refinement functions, and on the other hand of the precise enabling conditions of the operations on the different levels of abstraction. Each of the three specification levels is enriched with a permission system for reading, writing, or executing, and the refinement relations between these permission systems are explored. Files and directories are distinguished from the outset, but this rarely affects our part of the specifications. All results have been verified with the proof assistant PVS, in particular, that the invariants are preserved by the operations, and that, where the invariants hold, the operations commute with the refinement functions.     

High-performance temperature-programmed microfabricated gas chromatography columns

This paper reports the first development of high-performance, silicon-glass micro-gas chromatography (/spl mu/GC) columns having integrated heaters and temperature sensors for temperature programming, and integrated pressure sensors for flow control. These 3-m long, 150-/spl mu/m wide and 250-/spl mu/m deep columns, integrated on a 3.3 cm square die, were fabricated using a silicon-on-glass dissolved wafer process. Demonstrating the contributions to heat dissipation from conduction, convection, and radiation with and without packaging, it is shown that using a 7.5-mm high atmospheric pressure package reduces power consumption to about 650 mW at 100/spl deg/C, while vacuum packaging reduces the steady-state power requirements to less than 100 mW. Under vacuum conditions, 600 mW is needed for a temperature-programming rate of 40/spl deg/C/min. The 2300 ppm//spl deg/C TCR of the temperature sensors and the 50 fF/kPa sensitivity of the pressure sensors satisfy the requirements needed to achieve reproducible separations in a /spl mu/GC system. Using these columns, highly resolved 20-component separations were obtained with analysis times that are a factor of two faster than isothermal responses.     

High-transfer-rate high-capacity holographic disk data-storage system

We describe the design and implementation of a high-data-rate high-capacity digital holographic storage disk system. Various system design trade-offs that affect density and data-rate performance are described and analyzed. In the demonstration system that we describe, high-density holographic recording is achieved by use of high-resolution short-focal-length optics and correlation shift multiplexing in photopolymer disk media. Holographic channel decoding at a 1-Gbit/s data rate is performed by custom-built electronic hardware. A benchmark sustained optical data-transfer rate of 10 Gbits/s has been successfully demonstrated.