Source author record

Lisbeth Fajstrup

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Distributed, Parallel, and Cluster Computing Computational Geometry math.AT

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Combinatorial Conditions for Directed Collapsing

The purpose of this article is to study directed collapsibility of directed Euclidean cubical complexes. One application of this is in the nontrivial task of verifying the execution of concurrent programs. The classical definition of collapsibility involves certain conditions on a pair of cubes of the complex. The direction of the space can be taken into account by requiring that the past links of vertices remain homotopy equivalent after collapsing. We call this type of collapse a link-preserving directed collapse. In this paper, we give combinatorially equivalent conditions for preserving the topology of the links, allowing for the implementation of an algorithm for collapsing a directed Euclidean cubical complex. Furthermore, we give conditions for when link-preserving directed collapses preserve the contractability and connectedness of directed path spaces, as well as examples when link-preserving directed collapses do not preserve the number of connected components of the path space between the minimum and a given vertex.

preprint2022arXiv

Cut-off Theorems for the PV-model

We prove cut-off results for deadlocks and serializability of a $PV$ -thread $T$ run in parallel with itself: For a $PV$ thread $T$ which accesses a set $\mathcal{R}$ of resources, each with a maximal capacity $κ:\mathcal{R}\to\mathbb{N}$ , the PV-program $T^n$ , where $n$ copies of $T$ are run in parallel, is deadlock free for all $n$ if and only if $T^M$ is deadlock free where $M=Σ_{r\in\mathcal{R}}κ(r)$ . This is a sharp bound: For all $κ:\mathcal{R}\to\mathbb{N}$ and finite $\mathcal{R}$ there is a thread $T$ using these resources such that $T^M$ has a deadlock, but $T^n$ does not for $n<M$ . Moreover, we prove a more general theorem: There are no deadlocks in $p=T1|T2|\cdots |Tn$ if and only if there are no deadlocks in $T_{i_1}|T_{i_2}|\cdots |T_{i_M}$ for any subset $\{i_1,\ldots,i_M\}\subset [1:n]$ . For $κ(r)\equiv 1$ , $T^n$ is serializable for all $n$ if and only if $T^2$ is serializable. For general capacities, we define a local obstruction to serializability. There is no local obstruction to serializability in $T^n$ for all $n$ if and only if there is no local obstruction to serializability in $T^M$ for $M=Σ_{r\in\mathcal{R}}κ(r)+1$ . The obstructions may be found using a deadlock algorithm in $T^{M+1}$ . These serializability results also have a generalization: If there are no local obstructions to serializability in any of the $M$ -dimensional sub programs, $T_{i_1}|T_{i_2}|\cdots |T_{i_M}$ , then $p$ is serializable.

preprint2012arXiv

Trace Spaces: an Efficient New Technique for State-Space Reduction

State-space reduction techniques, used primarily in model-checkers, all rely on the idea that some actions are independent, hence could be taken in any (respective) order while put in parallel, without changing the semantics. It is thus not necessary to consider all execution paths in the interleaving semantics of a concurrent program, but rather some equivalence classes. The purpose of this paper is to describe a new algorithm to compute such equivalence classes, and a representative per class, which is based on ideas originating in algebraic topology. We introduce a geometric semantics of concurrent languages, where programs are interpreted as directed topological spaces, and study its properties in order to devise an algorithm for computing dihomotopy classes of execution paths. In particular, our algorithm is able to compute a control-flow graph for concurrent programs, possibly containing loops, which is "as reduced as possible" in the sense that it generates traces modulo equivalence. A preliminary implementation was achieved, showing promising results towards efficient methods to analyze concurrent programs, with very promising results compared to partial-order reduction techniques.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.