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.     

Platform‐independent profiling in a virtual execution environment

Virtual execution environments, such as the Java virtual machine, promote platform‐independent software development. However, when it comes to analyzing algorithm complexity and performance bottlenecks, available tools focus on platform‐specific metrics, such as the CPU time consumption on a particular system. Other drawbacks of many prevailing profiling tools are high overhead, significant measurement perturbation, as well as reduced portability of profiling tools, which are often implemented in platform‐dependent native code. This article presents a novel profiling approach, which is entirely based on program transformation techniques, in order to build a profiling data structure that provides calling‐context‐sensitive program execution statistics. We explore the use of platform‐independent profiling metrics in order to make the instrumentation entirely portable and to generate reproducible profiles. We implemented these ideas within a Java‐based profiling tool called JP. A significant novelty is that this tool achieves complete bytecode coverage by statically instrumenting the core runtime libraries and dynamically instrumenting the rest of the code. JP provides a small and flexible API to write customized profiling agents in pure Java, which are periodically activated to process the collected profiling information. Performance measurements point out that, despite the presence of dynamic instrumentation, JP causes significantly less overhead than a prevailing tool for the profiling of Java code. Copyright © 2008 John Wiley & Sons, Ltd.     

Structural reliability assessment based on probability and convex set mixed model

This paper investigates the reliability assessment of structures exhibiting both stochastic and bounded uncertainties by using a probability and convex set mixed model. The safety measure of a structure is quantified by a reliability index defined by a nested minimization problem. An iterative procedure is developed for seeking the worst-case point and the most probable failure point in the standard uncertainty space. Numerical examples are given to demonstrate the applicability of the probability and convex set mixed model representation in the structural reliability assessment, as well as to illustrate the validity and effectiveness of the proposed numerical method.     

Complete discriminant evaluation and feature extraction in kernel space for face recognition

This work proposes a method to decompose the kernel within-class eigenspace into two subspaces: a reliable subspace spanned mainly by the facial variation and an unreliable subspace due to limited number of training samples. A weighting function is proposed to circumvent undue scaling of eigenvectors corresponding to the unreliable small and zero eigenvalues. Eigenfeatures are then extracted by the discriminant evaluation in the whole kernel space. These efforts facilitate a discriminative and stable low-dimensional feature representation of the face image. Experimental results on FERET, ORL and GT databases show that our approach consistently outperforms other kernel based face recognition methods.

Implementation of a Gaussian process-based machine learning grasp predictor

With the goal of advancing the state of automatic robotic grasping, we present a novel approach that combines machine learning techniques and physical validation on a robotic platform to develop a comprehensive grasp predictor. After collecting a large grasp sample set (522 grasps), we first conduct a statistical analysis of the predictive ability of grasp quality metrics that are commonly used in the robotics literature. We then apply principal component analysis and Gaussian process (GP) algorithms on the grasp metrics that are discriminative to build a classifier, validate its performance, and compare the results to existing grasp planners. The key findings are as follows: (i) several of the existing grasp metrics are weak predictors of grasp quality when implemented on a robotic platform; (ii) the GP-based classifier significantly improves grasp prediction by combining multiple grasp metrics to increase true positive classification at low false positive rates; (iii) The GP classifier can be used generate new grasps to improve bad grasp samples by performing a local search to find neighboring grasps which have improved contact points and higher success rate.     

Actions Arising from Intersection and Union

An action is a pair of sets, C and S, and a function \(f:C\times S \rightarrow C\). Rothschild and Yalcin gave a simple axiomatic characterization of those actions arising from set intersection, i.e. for which the elements of C and S can be identified with sets in such a way that elements of S act on elements of C by intersection. We introduce and axiomatically characterize two natural classes of actions which arise from set intersection and union. In the first class, the \(\uparrow \!\!\downarrow \)-actions, each element of S is identified with a pair of sets \((s^\downarrow ,s^\uparrow )\), which act on a set c by intersection with \(s^\downarrow \) and union with \(s^\uparrow \). In the second class, the \(\uparrow \!\!\downarrow \)-biactions, each element of S is labeled as an intersection or a union, and acts accordingly on C. We give intuitive examples of these actions, one involving conversations and another a university’s changing student body. The examples give some motivation for considering these actions, and also help give intuitive readings of the axioms. The class of \(\uparrow \!\!\downarrow \)-actions is closely related to a class of single-sorted algebras, which was previously treated by Margolis et al., albeit in another guise (hyperplane arrangements), and we note this connection. Along the way, we make some useful, though very general, observations about axiomatization and representation problems for classes of algebras.     

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.     

Invariant ellipsoid method for minimization of unmatched disturbances effects in sliding mode control

A new sliding mode control design algorithm for a linear and a class of nonlinear quasi-Lipschitz disturbed system is presented. It is based on the appropriate selection of the sliding surface via invariant ellipsoid method. The designed control guarantees minimization of unmatched disturbances effects to system motions in a sliding mode. The obtained theoretical results are approved by numerical simulations.     

DOLAR: virtualizing heterogeneous information spaces to support their expansion

Users expect applications to successfully cope with the expansion of information as necessitated by the continuous inclusion of novel types of content. Given that such content may originate from ‘not‐seen thus far’ data collections and/or data sources, the challenging issue is to achieve the return of investment on existing services, adapting to new information without changing existing business‐logic implementation. To address this need, we introduce DOLAR (Data Object Language And Runtime), a service‐neutral framework which virtualizes the information space to avoid invasive, time‐consuming, and expensive source‐code extensions that frequently break applications. Specifically, DOLAR automates the introduction of new business‐logic objects in terms of the proposed virtual ‘content objects’. Such user‐specified virtual objects align to storage artifacts and help realize uniform ‘store‐to‐user’ data flows atop heterogeneous sources, while offering the reverse ‘user‐to‐store’ flows with identical effectiveness and ease of use. In addition, the suggested virtual object composition schemes help decouple business logic from any content origin, storage and/or structural details, allowing applications to support novel types of items without modifying their service provisions. We expect that content‐rich applications will benefit from our approach and demonstrate how DOLAR has assisted in the cost‐effective development and gradual expansion of a production‐quality digital library. Experimentation shows that our approach imposes minimal overheads and DOLAR‐based applications scale as well as any underlying datastore(s). Copyright © 2011 John Wiley & Sons, Ltd.     

Fully-adaptive algorithms for long-lived renaming

Long-lived renaming allows processes to repeatedly get distinct names from a small name space and release these names. This paper presents two long-lived renaming algorithms in which the name a process gets is bounded above by the number of processes currently occupying a name or performing one of these operations. The first algorithm is asynchronous, uses LL/SC objects, and has step complexity that is linear in the number of processes, c, currently getting or releasing a name. The second is synchronous, uses registers and counters, and has step complexity that is polylogarithmic in c. Both tolerate any number of process crashes.