Intro: State space and trace space

Simplicial models for trace spaces

Martin Raussen

Department of Mathematical Sciences Aalborg University

Denmark

Applied Algebraic Topology FIM, ETH Zürich 8.7.2011

Content

Higher Dimensional Automata: Examples ofstate spaces and associatedpath spaces

Motivation: Concurrency

A simple case: State spaces and path spaces related to linear PV-programs

Tool: Cutting up path spaces intocontractiblesubspaces Homotopy type of path space described by amatrix poset categoryand realized by aprodsimplicial complex

Algorithmics: Detectingdeadandalive subcomplexes/matrices

Outlook: How to handlegeneral HDA.

Intro: State space and trace space

Problem: How are they related?

Example 1: State space and trace space for a semaphore space

State space= a 3D cube~_I³\F

minus 4 box obstructions

Path space modelcontained in a torus(∂∆²)²–

homotopy equivalent to a wedge of two circles and a point: (S¹∨S¹)t ∗

Intro: State space and trace space

Pre-cubical set as state space

Example 2: State space and trace space for a non-looping semi-cubical complex

State space:Boundaries of two cubes glued together at common squareAB⁰C⁰•

Path spacemodel:

Prodsimplicial complex contained in torus(_∂∆²)²– homotopy equivalent to S¹∨S¹

Intro: State space and trace space

with loops

Example 3: Torus with a hole

• • • •

• •

X

• •

• N • •

• • • •

State space with hole:

2D torus∂∆²×_∂∆²with a rectangle∆¹×_∆¹removed

Path spacemodel:

Discrete infinite space of dimension 0 corresponding to{r,u}^∗

Motivation: Concurrency

Semaphores: A simple model for mutual exclusion Mutual exclusion

occurs, whennprocessesP_i compete formresourcesR_j.

Onlyk processes can be served at any given time.

Semaphores

Semantics: A processor has to lock a resource and to relinquish the lock later on!

Description/abstractionP_i : . . .PR_j. . .VR_j. . . (E.W. Dijkstra) P: pakken;V: vrijlaten

A geometric model: Schedules in "progress graphs"

The Swiss flag example

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111

000000000000000000 111111111111111111 00

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0

11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 1

Unsafe Un−

reachable

T1 T2

Pa Pb Vb Va

Pb Pa Va Vb

(0,0)

(1,1)

PV-diagram from P₁ :PaP_bV_bVa

P₂ :P_bP_aV_aV_b

Executions aredirected paths– since time flow is irreversible – avoiding a forbidden region(shaded).

Dipaths that aredihomotopic (through a 1-parameter deformation consisting of dipaths) correspond to equivalentexecutions.

Deadlocks, unsafeand unreachableregions may occur.

Simple Higher Dimensional Automata

Semaphore models The state space

Alinear PV-program is modeled as the complement of a forbidden regionFconsisting of a number ofholesin ann-cube Iⁿ:

Hole= isothetic hyperrectangle

Rⁱ =]aⁱ₁,b₁ⁱ[× · · · ×]aⁱ_n,b_nⁱ[,1≤i ≤l, in ann-cube:

with minimal vertexaⁱ and maximal vertexbⁱ. State spaceX=~Iⁿ\F, F =^Sl_i=1Rⁱ

Xinherits a partial order from~Iⁿ.

More general (PV)-programs:

Replace~Iⁿby a productΓ1× · · · ×Γnofdigraphs.

Holes have then the formp₁ⁱ((0,1))× · · · ×p_nⁱ((0,1))with pⁱ_j :~I→Γj a directed injective (d-)path.

Pre-cubical complexes: like pre-simplicial complexes, with (partially ordered) hypercubes instead of simplices as building blocks.

Spaces of d-paths/traces – up to dihomotopy

the interesting spaces Definition

X ad-space,a,b ∈X.

p:~I →X ad-pathinX (continuous and

“order-preserving”) fromatob.

~P(X)(a,b)={p:~I →X|p(0) =a,p(b) =1,pa d-path}.

Trace space~T(X)(a,b)=~P(X)(a,b)modulo increasing reparametrizations.

In most cases:~P(X)(a,b)'~T(X)(a,b).

Adihomotopyon~P(X)(a,b)is a mapH:~I×I →X such thatHt ∈~P(X)(a,b), t ∈I; ie a path in~P(X)(a,b).

Aim:

Description of thehomotopy typeof~P(X)(a,b)asexplicit finite dimensional prodsimplicial complex.

In particular: itspath components, ie the dihomotopy classes of d-paths (executions).

Tool: Covers of X and of ~ _P ( X )( 0, 1 )

by contractible or empty subspaces

X=~Iⁿ\F,F=^Sl_i=1Rⁱ;Rⁱ = [aⁱ,bⁱ];0,1the two corners inIⁿ. Definition

X_j1,...,jl ={x∈X| ∀i:x_ji ≤aⁱ_j

i∨ ∃k:x_k≥bⁱ_k}

={x∈X| ∀i:x≤bⁱ ⇒x_ji≤aⁱ_j

i}, 1≤j_i ≤n.

Examples:

A cover:

~P(X)(0,1) = ^[

1≤j₁,...,j_l≤n

~P(X_j1,...,jl)(0,1).

More intricate subspaces as intersections

either empty or contractible Definition

∅6=J₁,. . .,J_l ⊆[1:n]:

X_J1,...,Jl = ^\

ji∈J_i

X_j1,...,jl

= {x ∈X| ∀i,j_i ∈J_i :x ≤bⁱ ⇒x_ji ≤aⁱ_j

i}

Theorem

Every path space~_P(X_J1,...,Jl)(0,1)is eitheremptyor contractible.

Proof.

relies on: SubspacesX_J1,...,Jl areclosed under∨= l.u.b.

Question:

For whichJ₁,. . .,J_l ⊆[1:n]is~_P(X_J1,...,Jl)(0,1)6=_∅?

Combinatorics: Bookkeeping with binary matrices

Binary matrices

Ml,n poset(≤) ofbinaryl×n-matrices M_l,n^R no rowvector is thezerovector M_l,n^C every columnvector is aunitvector

Correspondences

Index sets ↔ Matrix sets (P([1:n]))^l ↔ Ml,n

J= (J1,. . .,Jl) 7→ M^J = (mij), mij=1⇔j∈Ji

J^M ← M J_i^M={j|mij =1} l-tuples of subsets6=_∅ ↔ M_l,n^R

{(K1,. . .,Kl)|[1:n] =^GKi} ↔ M_l,n^C

Question rephrased

XM :=XJM, ~_P(XM)(0,1) =~_P(XJM)(0,1)6=_∅?

A combinatorial model and its geometric realization

First examples

Combinatorics: poset category –

C(X)(0,1)⊆M_l,n^R ⊆M_l,n J ↔M ∈ C(X)(0,1)

Topology:prodsimplicial complex

T(X)(0,1)⊆(_∆ⁿ⁻¹)^l

∆^|_J^J₁^1|−1× · · · ×_∆^|_J^Jl|−1

l ⊆

T(X)(0,1)

⇔~_P(X_M)(0,1)6=_∅.

First examples

1 0 1 0

1 0 0 1

0 1 1 0

0 1 0 1

T(X₁)(0,1) = (_∂∆¹)²

=4∗

T(X₂)(0,1) =3∗

⊃ C(X)(0,1)

Further examples

State spaces and “alive” matrices

1 X =~_Iⁿ\~_Jⁿ

2

1 C(X)(0,1) =M_1,n^R \ {[1,. . .1]}. T(X)(0,1) =∂∆ⁿ⁻¹ 'Sⁿ⁻².

2 Cmax(X)(0,1) =

{

0 1 1

0 1 1

,

1 0 1

1 0 1

,

1 1 0

1 1 0

}. C(X)(0,1) ={M ∈M_l,n^R| ∃N∈ C_max(X)(0,1):M ≤N} T(X)(0,1) =3 diagonal squares⊂(_∂∆²)²=T²

'S¹. Many more examples in Goubault’s talk!

Homotopy equivalence between trace space

~ _T ( X )( 0, 1 ) and the prodsimplicial complex T ( X )( 0, 1 )

Theorem

~_P(X)(0,1)'T(X)(0,1)'_∆C(X)(0,1).

Proof.

FunctorsD,E,T :C(X)(0,1)^(op) →Top:

D(M) =~_P(XM)(0,1), E(M) =_∆^|_J^J1|−1

1 × · · · ×_∆^|_J^Jl|−1

l =_∆JM,

T(M) =∗

colimD=~_P(X)(0,1), colimE =T(X)(0,1), hocolimT =_∆C(X)(0,1).

The trivial natural transformationsD ⇒ T,E ⇒ T yield:

hocolimD ∼=hocolimT^∗∼=hocolimT ∼=hocolimE. Projection lemma:

hocolimD 'colimD, hocolimE 'colimE.

Why prodsimplicial?

rather than simplicial

We distinguish, for every obstruction,setsJ_i of restrictions.

A joint restriction is of typeJ₁× · · · ×J_l, and not an arbitrary subset of[1:n]^l.

Prodsimplicial and simplicial model (nerve of category) have the same number ofvertices (≤n^l)anddimension (≤(n−1)(l−1)−1).

The number of cells is of different orders:

prodsimplicial 2^nl simplicial 2^(nl)

From C ( X )( 0, 1 ) to properties of path space

Questions answered by homology calculations usingT(X)(0,1)

Questions

Is~_P(X)(0,1)path-connected, i.e., are all (execution) d-paths dihomotopic (lead to the same result)?

Determination ofpath-components?

Are componentssimply connected?

Other topological properties?

Strategies – Attempts

ImplementationofT(X)(0,1)in ALCOOL:

Progress at CEA/LIX-lab.: Goubault etal

The prodsimplicial structure onC(X)(0,1)↔T(X)(0,1) leads to an associatedchain complexof vector spaces over a field.

Use fast algorithms (eg Mrozek CrHom etc) to calculate thehomologygroups of these chain complexes even for very big complexes.

Number of path-components:rkH0(T(X)(0,1)). For path-components alone, there are faster “discrete”

methods, that also yield representatives in each path component: Goubault etal.

Even when “exponential explosion” prevents precise calculations, inductive determination (round by round) of general properties ((simple) connectivity) may be possible.

Detection of dead and alive subcomplexes

An algorithm starts with deadlocks and unsafe regions!

Allow less = forbid more!

RemoveextendedhyperrectanglesRⁱ_j

:= [0,bⁱ₁[× · · · ×[0,bⁱ_j−1[×]aⁱ_j,bⁱ_j[×[0,bⁱ_j+1[× · · · ×[0,b_nⁱ[⊃Rⁱ.

XM =X\ ^[

m_ij=1

R_jⁱ.

Theorem

The following are equivalent:

1 ~P(X_M)(0,1) =∅⇔M6∈C(X)(0,1).

2 There is a map i :[1:n]→[1:l]such that m_i(j),j =1^aand such that^T_1≤j≤nRⁱ_j^(j) 6=∅– giving rise to adeadlock unavoidable from0.

acorresponding to a matrixM(i)∈M_l,n^C withM(i)≤M

Partial orders and order ideals on matrix spaces

and an order preserving decision mapΨ

Dead or alive?

ConsiderΨ:M_l,n→Z/2, Ψ(M) =1⇔~_P(X_M)(0,1) =_∅. Ψ isorder preserving, in particular:

Ψ⁻¹(0),Ψ⁻¹(1)are closed in opposite senses:

M ≤N :Ψ(N) =0⇒_Ψ(M) =0;Ψ(M) =1⇒_Ψ(N) =1 (thusT(X)(0,1)prodsimplicial).

Ψ(M) =1⇔∃N ∈M_l,n^C such thatN≤M,Ψ(N) =1 D(X)(0,1) ={N ∈M_l,n^C|_Ψ(N) =1}–dead

C(X)(0,1) ={M ∈M_l,n^R|_Ψ(M) =0}–alive

Maximal alive – minimal dead

Still alive – not yet dead

Cmax(X)(0,1)⊂ C(X)(0,1)maximalalive matrices.

Matrices inCmax(X)(0,1)correspond tomaximal simplex productsinT(X)(0,1).

D_min(X)(0,1)=D(X)(0,1)∩M_l,n^C minimaldead matrices.

Connection: M ∈ C_max(X)(0,1),M ≤N a succesor (a single 0 replaced by a 1)⇒N ∈D_min(X)(0,1).

A cube removed from a cube

X =~_Iⁿ\~_Jⁿ_,D(X)(0,1) ={[1,. . .,1]}; Cmax(X)(0,1): vectors with a single 0;

C(X)(0,1) =M_l,n^R \ {[1,. . .,1]}; T(X)(0,1) =∂∆ⁿ⁻¹.

Dead matrices in D

( X )( 0, 1 )

Inequalities decide

Decisions: Inequalities

Enough to decide among thelⁿmatrices inM_l,n^C. A matrixM ∈M_l,n^C is described by a (choice) map

i :[1:n]→[1:l],m_i(j),j =1.

Deadlock algorithm inequalities:

M ∈D(X)(0,1)⇔aⁱ_j^(j) <b_j^i(k)for all 1≤j,k ≤n.

Algorithmic organisation: Choice maps with thesame imagegive rise to the sameupperboundsb_j^∗.

From D ( X ) to C

( X )

Minimal transversals in hypergraphs (simplicial complexes)

Incremental search: comparisons

ConstructCmax(X)(0,1)incrementally (checking for one matrix N∈D(X)(0,1)at a time), starting with matrix1:

1 N_i+16≤M ∈ Cⁱ(X)⇒M ∈ Cⁱ⁺¹(X);

2 N_i+1≤M ⇒M is replaced bynmatricesM^j with one additional 0. Example: X =~_Iⁿ\~_Jⁿ_.

Minimal transversals in a hypergraph

A matrix inD(X)(0,1)describes ahyperedgeon the vertex set[1:l]×[1:n];D(X)(0,1)describes ahypergraph.

Atransversalin a hypergraph is a vertex set that has non-empty intersection with each hyperedge.

Complements of minimal transversals correpond to matrices inCmax(0,1)– algorithms well-developed.

Extensions

1. Obstruction hyperrectangles intersecting the boundary ofIⁿ - Components

More general linear semaphore state spaces

More general semaphores (intersection with the boundary ofIⁿallowed)

ndining philosophers: Trace space has 2ⁿ−2 components Different end points:~_P(X)(c,d)and iterative calculations Endcomplexesrather than end points (allowing processes not to respond..., Herlihy & Cie)

Same technique, modification of definition and calculation ofC(X)(−,−),D(X)(−,−)etc. ; cf preprint, submitted.

State space components

New light on definition and determination ofcomponentsof model spaceX.

Extensions

2a. Semaphores corresponding tonon-linearprograms:

Path spaces in product of digraphs Products of digraphs instead of~_Iⁿ_: Γ=_∏ⁿ_j=1Γj, state spaceX = _Γ\F,

F a product of generalized hyperrectanglesRⁱ.

~_P(_Γ)(x,y) =_∏~_P(_Γj)(x_j,y_j)–homotopy discrete!

Pullback to linear situation

Represent apath componentC ∈~_P(_Γ)(x,y)by(regular) d-pathsp_j ∈~_P(_Γj)(x_j,y_j)– an interleaving.

The mapc:~_Iⁿ→_Γ,c(t₁,. . .,t_n) = (c₁(t₁),. . .,c_n(t_n))induces ahomeomorphism◦c :~_P(~_Iⁿ)(0,1)→C⊂~_P(_Γ)(x,y).

Extensions

2b. Semaphores: Topology of components of interleavings Homotopy types of interleaving components Pull backF viac:

X¯ =~_Iⁿ\F^¯,F¯ =^SR^¯i,R¯ⁱ =c⁻¹(Rⁱ)– honest hyperrectangles!

iX :~_P(X),→~_P(Γ).

Given a componentC⊂~_P(_Γ)(x,y).

The d-mapc : ¯X →Xinduces a homeomorphism c◦:~_P(X^¯)(0,1)→i_X⁻¹(C)⊂~_P(X)(x,y).

C“lifts toX”⇔~_P(X^¯)(0,1)6=_∅; if so:

Analysei_X⁻¹(C)via~_P(X^¯)(0,1).

Exploit relations between various components.

Special case:Γ= (S¹)ⁿ– a torus

State space: A torus with rectangular holes inF: Investigated by Fajstrup, Goubault, Mimram etal.:

Analyse bylanguageon the alphabetC(X)(0,1)ofalive matrices for a one-fold delooping ofΓ\F.

Extensions

3a. D-paths in pre-cubical complexes

HDA: Directed pre-cubical complex

Higher Dimensional Automaton: Pre-cubical complex– like simplicial complex but withcubesas building blocks – with preferred diretions.

Geometric realizationX with d-space structure.

Branch points and branch cubes

These complexes havebranch pointsandbranch cells–more than onemaximal cell with same lower corner vertex.

At branch points, one can cut up a cubical complex in simpler pieces.

Trouble: Simpler pieces may havehigher order branch points.

Extensions

3b. Path spaces for HDAs without d-loops Non-branching complexes

Start with complex without directed loops: After finally many iterations: SubcomplexY withoutbranch points.

Theorem

~_P(Y)(x₀,x₁)isemptyorcontractible.

Proof.

Such a subcomplex has a preferred diagonal flow and a contraction from path space to the flow line from start to end.

Results in a (complicated) finite categoryM(X)(x0,x1)on subsets of (iterated) branch cells.

Theorem

~_P(X)(x0,x1)is homotopy equivalent to the nerve N(M(X)(x0,x1))of that category.

Extensions

3c. Path spaces for HDAs with d-loops

Delooping HDAs

A pre-cubical complex comes with anL₁-length 1-form ω=dx₁+· · ·+dx_non everyn-cube.

Integration:L₁-length on rectifiable paths,homotopy invariant.

Definesl:P(X)(x₀,x₁)→Randl_] :π1(X)→Rwith kernelK. The (usual) coveringX˜ ↓X withπ1(X^˜) =K is adirected pre-cubical complexwithoutdirected loops.

Theorem (Decomposition theorem)

For every pair of pointsx₀,x₁ ∈X , path space~_P(X)(x₀,x₁)is homeomorphic to the disjoint union^F_n∈Z~_P(X^˜)(x⁰₀,xⁿ₁)^a.

ain the fibres overx₀,x₁

To conclude

From a (rather compact) state space model to afinite dimensional tracespace model.

Calculations of invariants (Betti numbers) possible even for quite large state spaces.

Dimension of trace space model reflectsnotthesizebut thecomplexityof state space (number of obstructions, number of processors) –linearly.

Challenge: General properties of path spaces for algorithms solving types of problems in adistributed manner?

(Connection to the work of Herlihy and Rajsbaum)

Want to know more?

Thank you!

Eric Goubault’s talk this afternoon!

References

MR,Simplicial models for trace spaces, AGT10(2010), 1683 – 1714.

MR,Execution spaces for simple higher dimensional automata, Aalborg University Research Report R-2010-14;

submitted

MR,Simplicial models for trace spaces II: General HDA, Draft.

Fajstrup,Trace spaces of directed tori with rectangular holes, Aalborg University Research Report R-2011-08.

Fajstrup etal.,Trace Spaces: an efficient new technique for State-Space Reduction, submitted.

Rick Jardine,Path categories and resolutions, Homology, Homotopy Appl.12(2010), 231 – 244.

Thank you for your attention!