Narrow Results

This paper is focused on concurrent objects (objects shared by concurrent processes). It introduces a consistency condition called Normality whose definition is based only on local orders of operations as perceived by processes and by objects. First we consider the model in which each operation is on exactly one object. In this model we show that a history is linearizable iff it is normal. However, the definition of Normality is less constraining in the sense that there are strictly more legal sequential histories which are considered equivalent to the given history when Normality is used. We next consider a more general model where operations can span multiple objects. In this model we show that Normality is strictly weaker than Linearizability, i.e., history may be normal but not linearizable. As Normality refers only to local orders (process order and object order) it appears to be well-suited to objects supported by asynchronous distributed systems and accessed by RPC-like mechanisms.

We develop and apply the theory of lower and upper compensated convex transforms introduced in [K. Zhang, Compensated convexity and its applications, Ann. Inst. H. Poincaré Anal. Non Linéaire25 (2008) 743–771] to define multiscale, parametrized, geometric singularity extraction transforms of ridges, valleys and edges of function graphs and sets in ℝⁿ. These transforms can be interpreted as "tight" opening and closing operators, respectively, with quadratic structuring functions. We show that these geometric morphological operators are invariant with respect to translation, and stable under curvature perturbations, and establish precise locality and tight approximation properties for compensated convex transforms applied to bounded functions and continuous functions. Furthermore, we establish multiscale and Hausdorff stable versions of such transforms. Specifically, the stable ridge transforms can be used to extract exterior corners of domains defined by their characteristic functions. Examples of explicitly calculated prototype mathematical models are given, as well as some numerical experiments illustrating the application of these transforms to 2d and 3d objects.

We apply compensated convex transforms to define a multiscale Hausdorff stable method to extract intersections between smooth compact manifolds represented by their characteristic functions or as point clouds embedded in ℝⁿ. We prove extraction results on intersections of smooth compact manifolds and for points of high curvature. As a result of the Hausdorff–Lipschitz continuity of our transforms, we show that our method is stable against dense sampling of smooth manifolds with noise. Examples of explicitly calculated prototype models for some simple cases are presented, which are also used in the proofs of our main results. Numerical experiments in two- and three-dimensional space, and applications to geometric objects are also shown.