text:
# Nonlinear superconformal symmetry of a fermion in the field of a Dirac monopole

## 1 Introduction

Hidden, or dynamical symmetries are behind the special properties of some classical and quantum mechanical systems. The best known example of the hidden symmetry is provided, probably, by the Kepler problem. Being associated with the Laplace-Runge-Lenz vector integral, it is responsible for the closed character of the finite orbits, fixing the orbits’ orientation in the both cases of a finite and an infinite motion. Also, it explains a degeneracy of the quantum spectrum.

The problem of identification of symmetries of the fermion-monopole system is a long-standing puzzle. More than twenty years ago, Jackiw found that the system of a scalar charged particle in the field of a Dirac magnetic monopole possesses a hidden conformal $`so(1,2)`$ symmetry . Four years later D’Hoker and Vinet showed that the fermion-monopole system can be characterized by the $`osp(1,2)`$ supersymmetry . Then, De Jonghe, Macfarlane, Peeters and van Holten  identified a new supersymmetry of the system which squares to the (shifted) Casimir invariant of the full rotation group. Their analysis, based on a general method which uses Killing-Yano tensors to generate additional supersymmetries , revealed that the full supersymmetry algebra of the fermion-monopole is, in fact, nonlinear. Lately, Spector  found that such a non-standard nonlinear supersymmetry associated with the Casimir invariant of the full rotation group may exist even when an additional potential term breaking a usual supersymmetry is included in the Pauli Hamiltonian. In both papers , the supersymmetries were treated outside the context of conformal symmetry. Following their line, in Ref.  it was argued that the commutator of the usual (“square root from the Hamiltonian”) and of the non-standard (“square root from the rotational Casimir”) supercharges should also be treated as a new supercharge, which squares for the product of the Hamiltonian and rotational Casimir invariant111See Eq. (3.28) and the comment to it.. This resembles the nonlinear structure of the Kepler problem, where the commutator of the Laplace-Runge-Lenz vector components takes a form of the product of the Hamiltonian and angular momentum operator .

The $`osp(1,2)`$ symmetry of the fermion-monopole system  supplied with the additional nonlinear supersymmetry of Refs.  is in the obvious but puzzling contrast with the $`osp(2,2)`$ supersymmetry of the Akulov-Pashnev-Fubini-Rabinovici superconformal model . The difference is rather surprising since the both systems are characterized by the same Lie algebraic dynamical structure $`so(1,2)`$, and their quantum spaces associated with the spin degrees of freedom are exactly the same. Recently, however, it was observed  that for the special (discrete) values of the fermion-boson coupling parameter, in addition to the usual $`osp(2,2)`$ symmetry, the superconformal model  can be characterized by a hidden nonlinear superconformal symmetry.

In the present paper, we investigate the problem of identification of (super)symmetries of the fermion-monopole system by comparing its structure with realization of superconformal symmetry in the model . As a result, it will be shown that the system possesses a nonlinear superconformal symmetry. A nonlocal transformation applied to the states with the angular momentum different from the lowest one, reduces the full symmetry to the usual $`osp(2,2)`$ supersymmetry (plus a ‘decoupled’ rotational symmetry) , in which the square root from the shifted rotational Casimir invariant plays the role of the central charge similar to the boson-fermion coupling constant of the superconformal model .

The paper is organized as follows. In section 2 we analyze the dynamical symmetry of the superconformal mechanics model. The results of the analysis are applied in section 3 to find all the set of the integrals generating the dynamical symmetry of the fermion-monopole system and to identify the corresponding superalgebra at the classical and quantum levels. In section 4 we summarize the obtained results and discuss some open problems to be interesting for further investigation.

## 2 Dynamical symmetry of the 1D superconformal mechanics

We start with a short discussion of the symmetries of the 1D superconformal model , that will be helpful for subsequent identification of the fermion-monopole symmetries.

The classical model  is given by the Hamiltonian

$$H=\frac{1}{2}\left(p^2+\frac{\alpha (\alpha +2i\psi _1\psi _2)}{x^2}\right),$$
(2.1)
and by the fundamental Poisson brackets $`\{x,p\}=1`$, $`\{\psi _a,\psi _b\}=i\delta _{a,b}`$, $`a,b=1,2`$. In addition to $`H`$, the system possesses the even,

$$D=\frac{1}{2}xptH,K=\frac{1}{2}x^22tDt^2H,\mathrm{\Sigma }=i\psi _1\psi _2,$$
(2.2)
and odd,

$$Q_a=p\psi _a+\frac{\alpha }{x}ϵ_{ab}\psi _b,\stackrel{~}{Q}_a=x\psi _atQ_a,$$
(2.3)
integrals of motion obeying the equation of the form $`\frac{d}{dt}I=\frac{}{t}I+\{I,H\}=0`$. The set of integrals (2.1), (2.2), (2.3) generates the $`osp(2,2)`$ superalgebra given by the nontrivial Poisson bracket relations

$`\{H,K\}=2D,\{D,H\}=H,\{D,K\}=K,`$
$`\{Q_a,Q_b\}=2i\delta _{ab}H,\{\stackrel{~}{Q}_a,\stackrel{~}{Q}_b\}=2i\delta _{ab}K,`$
$`\{\stackrel{~}{Q}_a,Q_b\}=2i\delta _{ab}D+iϵ_{ab}(\mathrm{\Sigma }+\alpha ),`$ (2.4)
$`\{H,\stackrel{~}{Q}_a\}=Q_a,\{K,Q_a\}=\stackrel{~}{Q}_a,\{D,Q_a\}={\displaystyle \frac{1}{2}}Q_a,\{D,\stackrel{~}{Q}_a\}={\displaystyle \frac{1}{2}}\stackrel{~}{Q}_a,`$
$`\{\mathrm{\Sigma },Q_a\}=ϵ_{ab}Q_b,\{\mathrm{\Sigma },\stackrel{~}{Q}_a\}=ϵ_{ab}\stackrel{~}{Q}_b.`$
For convenience of comparison with the fermion-monopole system, we do not include a constant $`\alpha `$, playing a role of the central element of the superalgebra, in the definition of the $`osp(2|2)`$ spin integral $`\mathrm{\Sigma }`$ generating the $`so(2)u(1)`$ rotations of the supercharges. The quantity

$$C=4(D^2KH)2\alpha \mathrm{\Sigma }+\alpha ^2$$
(2.5)
is the Casimir element of the superalgebra (2.4) taking here the value $`C=0`$.

Since the system is described by the two independent odd (Grassmann) variables $`\psi _a`$, $`a=1,2`$, not all the odd integrals (2.3) are independent. Using the explicit form of the integrals (2.1), (2.2), (2.3), one finds that they satisfy the odd and even relations

$$\alpha Q_a+2ϵ_{ab}(Q_bD\stackrel{~}{Q}_bH)=0,\alpha \stackrel{~}{Q}_a+2ϵ_{ab}(Q_bK\stackrel{~}{Q}_bD)=0,$$
(2.6)
$$Q_1Q_22i\mathrm{\Sigma }H=0,\stackrel{~}{Q}_1\stackrel{~}{Q}_22i\mathrm{\Sigma }K=0,Q_a\stackrel{~}{Q}_b+i\delta _{ab}\alpha \mathrm{\Sigma }2iϵ_{ab}\mathrm{\Sigma }D=0.$$
(2.7)
The set of quadratic combinations defined by Eqs. (2.6), (2.7) is transformed linearly under the action of the $`osp(2,2)`$ generators. If the relations (2.6) are treated as a homogeneous linear set of equations for $`Q_a`$ and $`S_a`$, then due to the equality $`C=0`$ and nilpotent character of $`\mathrm{\Sigma }`$, its determinant $`\mathrm{\Delta }=(C+2\alpha \mathrm{\Sigma })^2`$ takes a zero value. And vice versa, the condition $`\mathrm{\Delta }=0`$ for the determinant of the homogeneous system of equations for $`Q_a`$ and $`\stackrel{~}{Q}_a`$ (2.6) fixes the value of the classical Casimir element: $`C=0`$.

It is useful to look at the symmetries of the one-dimensional model (2.1) from the viewpoint of the planar system of a free spin-$`1/2`$ particle given by the action

$$A=\left(\frac{1}{2}\dot{x}_a^2\frac{i}{2}\dot{\psi }_a\psi _a\right)𝑑t$$
(2.8)
and reduced to the surface of the fixed full angular momentum . The system (2.8) can be characterized by the set of quadratic integrals

$$H=\frac{1}{2}p_a^2,K=\frac{1}{2}X_a^2,D=\frac{1}{2}X_ap_a,\mathrm{\Sigma }=\frac{i}{2}ϵ_{ab}\psi _a\psi _b,$$
(2.9)
$$L=ϵ_{ab}X_ap_b,$$

$$Q_1=p_a\psi _a,Q_2=ϵ_{ab}p_a\psi _b,\stackrel{~}{Q}_1=X_a\psi _a,\stackrel{~}{Q}_2=ϵ_{ab}X_a\psi _b$$
(2.10)
constructed from the obvious set of linear integrals of motion $`p_a`$, $`X_a=x_ap_at`$ and $`\psi _a`$. The integrals (2.9), (2.10) form a superalgebra of the form (2.4), in which instead of the parameter $`\alpha `$ the full angular momentum $`J=L+\mathrm{\Sigma }`$ plays the role of the central element. As a consequence, the system (2.1) may be obtained by reducing the system (2.8) to the surface of the constraint

$$J\alpha =0.$$
(2.11)
Due to zero Poisson brackets of the quadratic integrals (2.9), (2.10) with the constraint (2.11), they are observables, and after reduction their superalgebra takes exactly the form (2.4), while the integrals themselves take the form of the corresponding integrals (2.1)–(2.3) (for the details see ref. ).

One can introduce into the system one more odd degree of freedom described by the Grassmann variable $`\psi _3`$ if to add the kinetic term $`\frac{i}{2}\dot{\psi }_3\psi _3`$ into the Lagrangian of the system (2.8). With such an extension, classically the system will be described by one more odd integral of motion $`\mathrm{\Gamma }=\psi _3`$ being also, due to the relation $`\{\psi _3,J\}=0`$, the observable variable. This additional odd integral satisfies the relation $`\{\mathrm{\Gamma },\mathrm{\Gamma }\}=i1`$, and has zero Poisson brackets with all the even and odd integrals (2.9), (2.10). With respect to the superalgebra $`osp(2|2)`$, the additional integral $`\mathrm{\Gamma }`$ may be interpreted as a classical analog of the quantum grading operator. Indeed, at the quantum level, the Grassmann variables satisfying the Poisson bracket relations $`\{\psi _a,\psi _b\}=i\delta _{ab}`$ are transformed into the generators of the Clifford algebra $`Cl_2`$ (for the initial system with $`\psi _a`$, $`a=1,2`$), or of the $`Cl_3`$ (for the extended system with the three odd variables $`\psi _a`$, $`a=1,2,3`$). Here, in correspondence with the relation $`dimCl_{2n+1}=dimCl_{2n}=2^n`$ for the dimensions of irreducible representations, in both cases the quantum analogs of the odd variables can be realized in terms of Pauli matrices, $`\widehat{\psi }_a=\sqrt{\frac{\mathrm{}}{2}}\sigma _a`$, and $`\sigma _3\widehat{\psi }_3`$ is identified as a grading operator of the quantum $`osp(2|2)`$ superalgebra.

Up to a numerical factor the integral $`\widehat{\mathrm{\Sigma }}=\frac{i}{2}[\widehat{\psi }_1,\widehat{\psi }_2]=\frac{\mathrm{}}{2}\sigma _3`$ coincides with the integral $`\widehat{\psi }_3`$ of the extended system. Hence, the integral $`\widehat{\mathrm{\Sigma }}=\frac{\mathrm{}}{2}\sigma _3`$ of the 1D superconformal model (2.1) may be treated not only as an even generator of the $`osp(2|2)`$, but simultaneously it may be considered as a grading operator of the superconformal algebra.

Note that at the quantum level, the condition of existence of a nontrivial solution to the system of equations (2.6) is reduced to the equation

$$\left(\widehat{C}\frac{3}{4}\mathrm{}^2\right)\left(\widehat{C}\frac{3}{4}\mathrm{}^2+8\mathrm{}\alpha \sigma _3\right)=0,$$

which fixes the value of the quantum analog of the Casimir element (2.5),

$$\widehat{C}4\widehat{D}^22(\widehat{K}\widehat{H}+\widehat{H}\widehat{K})+\alpha (\alpha \mathrm{}\sigma _3)=\frac{3}{4}\mathrm{}^2.$$
(2.12)
## 3 Dynamical symmetry of the fermion-monopole

The 3D fermion-monopole system is described by the Hamiltonian

$$H=\frac{1}{2}P_i^2eB_iS_i$$
(3.1)
with $`P_i=p_ieA_i`$, $`B_i=ϵ_{ijk}_jA_k=gx_i/|x|^3`$, $`|x|=\sqrt{x_ix_i}`$, $`S_j=\frac{i}{2}ϵ_{jkl}\psi _k\psi _l`$, and by the fundamental Poisson brackets $`\{x_i,p_j\}=\delta _{ij}`$, $`\{\psi _j,\psi _k\}=i\delta _{jk}`$. The Hamiltonian (3.1) and the quantities

$$D=\frac{1}{2}X_iP_i+etB_iS_i=\frac{1}{2}x_iP_itH,$$
(3.2)
$$K=\frac{1}{2}X_i^2et^2B_iS_i=\frac{1}{2}x_i^22tDt^2H$$
(3.3)
together with the full angular momentum $`J_i`$, given by the relations

$$J_i=L_i\nu n_i+S_i,L_i=ϵ_{ijk}x_jP_k,n_i=\frac{x_i}{|x|},\nu =eg,$$
(3.4)
constitute the set of integrals of motion generating the $`so(1,2)so(3)`$ symmetry . Here, the $`so(1,2)`$ Casimir element $`D^2KH`$ and the $`so(3)`$ rotational invariant are related by the equation

$$C=4(D^2KH)+𝒥2𝒬_L=0,$$
(3.5)
where

$$𝒥=J_i^2\nu ^2,$$
(3.6)
$$𝒬_L=L_iS_i.$$
(3.7)
The $`𝒬_L`$ is the integral of motion commuting with all the generators of the algebra $`so(1,2)so(3)`$, and extending it to the $`so(1,2)so(3)u(1)`$.

The odd, $`\psi _i`$, and the even (the fermion’s spin), $`S_i`$, nilpotent vectors satisfy the relations

$$\{S_i,\psi _j\}=ϵ_{ijk}\psi _k,\{S_i,S_j\}=ϵ_{ijk}S_k,\psi _iS_j=\frac{1}{3}\delta _{ij}(S_k\psi _k),$$
(3.8)
and their evolution is described by the same precession motion,

$$\frac{d}{dt}\psi _i=eϵ_{ijk}\psi _jB_k,\frac{d}{dt}S_i=eϵ_{ijk}S_jB_k.$$
(3.9)
Classically, they may be treated as “parallel” vectors, $`ϵ_{ijk}\psi _jS_k=0`$, and from eq. (3.9) one finds that their scalar product

$$Q_S=S_i\psi _i$$
(3.10)
is the odd integral of motion. Analogously to the 1D superconformal model, in irreducible representation the quantum operators $`\widehat{\psi }_i`$ and $`\widehat{S}_i`$ can be realized in terms of the Pauli matrices, $`\widehat{\psi }_i=\sqrt{\frac{\mathrm{}}{2}}\sigma _i`$, $`\widehat{S}_i=\frac{\mathrm{}}{2}\sigma _i`$, i.e., up to a numerical factor they are represented by the same operators $`\sigma _i`$. Hence, the quantum analog of the odd integral of motion (3.10) is reduced to a pure quantum constant: $`\widehat{Q}_S=3(\mathrm{}/2)^{3/2}`$.

Defining the vector $`X_i=x_itP_i`$, which in the free case $`eg=0`$ is reduced to the integral generating the Galilean boosts, one can construct the pair of odd quantities

$$Q_P=P_i\psi _i,Q_X=X_i\psi _i$$
(3.11)
satisfying the Poisson bracket relations

$$\{Q_P,Q_P\}=2iH,\{Q_X,Q_X\}=2iK,\{Q_X,Q_P\}=2iD.$$
(3.12)
For the components of the vector $`P_i`$ the classical relation

$$ϵ_{ijk}\{P_i,\{P_j,P_k\}\}\delta ^{(3)}(x)$$
(3.13)
takes place (see also refs. ), and the quantities (3.11) are the odd integrals of motion if the point $`x_i=0`$ is excluded from the configuration space. In a physical context, this can be achieved by some sort of ‘regularization’, e.g., by adding into the Hamiltonian a spherical reflecting barrier potential $`V(|x|)=+\mathrm{}`$ for $`|x|a`$, and $`V(|x|)=0`$ for $`|x|a>0`$, and by taking subsequently a limit $`a0`$; for alternative regularization see refs. . Here we are not interested in regularization and related problem of bounded states , and in what follows will assume simply that the point $`x_i=0`$ is excluded.

The odd integrals $`Q_P`$ and $`Q_X`$, being analogs of the integrals $`Q_1`$ and $`\stackrel{~}{Q}_1`$ of the superconformal model (cf. the structure of the integrals (3.11) with that of the integrals $`Q_1`$ and $`\stackrel{~}{Q}_1`$ given by eq. (2.10)), generate together with the $`H`$, $`K`$, $`D`$ and $`J_i`$ the $`osp(1,2)so(3)`$ superalgebra with the Casimir element (3.5), which was discussed by D’Hoker and Vinet . In the fermion-monopole system, however, there is also the nontrivial classical odd integral (3.10). Its bracket with the odd integrals (3.11) generates new even integrals

$$𝒬_P=P_iS_i,𝒬_X=X_iS_i.$$
(3.14)
The operators corresponding to the classical quantities (3.11) coincide up to a numerical factor with the quantum analogs of (3.14). But classically the sets (3.11) and (3.14) are different, and their mutual nontrivial Poisson brackets produce via the relation

$$\{Q_X,𝒬_P\}=\{𝒬_X,Q_P\}=Q_L+Q_S$$

a new integral of motion

$$Q_L=L_i\psi _i$$
(3.15)
being the odd counterpart of the even integral (3.7). Again, these two, $`𝒬_L`$ and $`Q_L`$, are related by the Poisson bracket with the integral (3.10), $`\{Q_S,Q_L\}=3i𝒬_L`$, and their quantum analogs are different only in a numerical factor proportional to $`\mathrm{}^{1/2}`$.

Let us change the integral $`Q_L`$ for the linear combination of $`Q_L`$ and $`Q_S`$,

$$Q_Y=Q_L+\frac{2}{3}Q_S.$$
(3.16)
It is this odd integral, satisfying the relation

$$\{Q_Y,Q_Y\}=i𝒥,$$

that was treated in Ref.  as a generator of a new supersymmetry. It, unlike the $`Q_L`$, has zero Poisson bracket relations (anticommutes at the quantum level) with the odd integrals (3.11). On the other hand, the Poisson brackets of the odd integrals (3.11) with the even integral $`𝒬_L`$, which due to the relation $`\{Q_S,Q_S\}=0`$ may be treated as an even counterpart of (3.16) as well, generate the two new odd integrals of motion,

$$\{𝒬_L,Q_P\}=Q_𝒫,\{𝒬_L,Q_X\}=Q_𝒳,$$

where

$$Q_𝒫=𝒫_i\psi _i,Q_𝒳=𝒳_i\psi _i,$$
(3.17)
$$𝒫_i=ϵ_{ijk}L_jP_k+\frac{2}{3}\nu |x|^1S_i,𝒳_i=ϵ_{ijk}L_jX_k\frac{2}{3}t\nu |x|^1S_i.$$
(3.18)
The brackets of the integrals (3.17) with (3.10) produce their even counterparts

$$𝒬_𝒫=𝒫_iS_i,𝒬_𝒳=𝒳_iS_i.$$

We list all the brackets of the nilpotent integrals, except the trivial brackets

$$\{Q_S,Q_S\}=\{Q_S,𝒬_L\}=0,$$

in the table.

The quantities $`Q_S`$, $`Q_Y`$ and $`𝒬_L`$ have zero Poisson brackets with the $`so(1,2)`$ generators (3.1), (3.2), (3.3), while the nontrivial brackets of the odd integrals (3.11) with the $`so(1,2)`$ generators are

$$\{D,Q_P\}=\frac{1}{2}Q_P,\{D,Q_X\}=\frac{1}{2}Q_X,\{K,Q_P\}=Q_X,\{H,Q_X\}=Q_P.$$
(3.19)
The pairs ($`Q_𝒫`$, $`Q_𝒳`$), ($`𝒬_P`$, $`𝒬_X`$), and ($`𝒬_𝒫`$, $`𝒬_𝒳`$), like the pair ($`Q_P`$, $`Q_X`$), form the spin-1/2 representations of the $`so(1,2)`$, i.e. their corresponding brackets with the $`H`$, $`K`$ and $`D`$ have a form similar to (3.19).

The odd integrals $`Q_P`$, $`Q_X`$, $`Q_𝒫`$ and $`Q_𝒳`$ satisfy the relations to be analogous to the relations (2.6), (2.7):

$`Q_P𝒥+2(Q_𝒫DQ_𝒳H)=0,Q_X𝒥2(Q_𝒳DQ_𝒫K)=0,`$
$`Q_𝒫2(Q_PDQ_XH)=0,Q_𝒳+2(Q_XDQ_PK)=0,`$ (3.20)
$`Q_PQ_𝒫2iH𝒬_L=0,Q_XQ_𝒳2iK𝒬_L=0,Q_PQ_X+2i𝒬_L=0,`$
$`Q_𝒫Q_𝒳i𝒬_L𝒥=0,Q_PQ_𝒳+2i𝒬_LD=0,Q_𝒫Q_X2i𝒬_LD=0.`$ (3.21)
Having in mind this similarity, and comparing the structure of the Poisson brackets of the integrals $`Q_P`$, $`Q_X`$, $`Q_𝒫`$, $`Q_𝒳`$, $`H`$, $`K`$, $`D`$ and $`𝒬_L`$ of the fermion-monopole system with that for the integrals $`Q_1`$, $`\stackrel{~}{Q}_1`$, $`Q_2`$, $`\stackrel{~}{Q}_2`$, $`H`$, $`K`$, $`D`$ and $`\mathrm{\Sigma }`$ of the superconformal model, we find that the former set of the integrals forms a nonlinear $`_2`$-graded Poisson algebra which can be considered as a nonlinear generalization of the superconformal algebra $`osp(2,2)`$.

Since $`𝒥`$ has zero Poisson brackets with all the integrals, it plays the role of the central charge of the nonlinear superconformal symmetry to be analogous to that for the $`\alpha ^2`$ in the superconformal model. From the comparison it follows also that the odd integral $`Q_Y`$ is similar to the odd integral $`\mathrm{\Gamma }`$ playing the role of the classical analog of the grading operator for the superconformal model. For $`L_i^20`$, the rescaling

$$Q_𝒫Q_𝒫𝒥^{1/2},Q_𝒳Q_𝒳𝒥^{1/2},𝒬_L𝒬_L𝒥^{1/2}$$
(3.22)
transforms the nonlinear superconformal algebra of the fermion-monopole system into the $`osp(2,2)`$ Lie superalgebra (2.4), in which the role of the parameter $`\alpha `$ is played by the $`𝒥^{1/2}`$.

For $`L_i^20`$, one can define the vector

$$N_i=\left(1\frac{2\nu }{L_j^2}S_kn_k\right)Y_i,Y_i=L_i+\frac{2}{3}S_i.$$

Then, using Eq. (3.4), the equality $`S_iS_j=0`$ and the last relation from Eq. (3.8), one can represent the integrals $`Q_𝒫`$, $`Q_𝒳`$, $`Q_Y`$ and $`𝒬_L`$ in the form

$$Q_𝒫=ϵ_{ijk}N_iP_j\psi _k,Q_𝒳=ϵ_{ijk}N_iX_j\psi _k,𝒬_L=\frac{i}{2}ϵ_{ijk}N_i\psi _j\psi _k,Q_Y=N_i\psi _i.$$
(3.23)
The ‘extended’ superconformal model may also be represented in a 3D form by introducing the notations $`x_i=(x_1,x_2,0)`$, $`p_i=(p_1,p_2,0)`$, $`\psi _i=(\psi _1,\psi _2,\psi _3)`$ and $`N_i=(0,0,1)`$. Then the integrals (2.9), (2.10) can be rewritten in the form of 3D scalar products, similar to the integrals of motion of the fermion-monopole system. In particular, the classical analog of the grading operator, $`\mathrm{\Gamma }=\psi _3`$, takes a form similar to $`Q_Y`$ from (3.23), $`\mathrm{\Gamma }=N_i\psi _i`$.

Identifying the $`_2`$-graded Poisson algebra of the integrals of motion as a nonlinear superconformal algebra (plus the ‘decoupled’ $`so(3)su(2)`$), we have omitted from consideration the even nilpotent integrals $`𝒬_X`$, $`𝒬_P`$, $`𝒬_𝒳`$ and $`𝒬_𝒫`$. This was done having in mind the quantum case, where these integrals are different from the quantum analogs of the corresponding odd integrals only in a simple numerical factor $`\sqrt{\mathrm{}/2}`$.

Let us note here that the even nilpotent integrals for the model of superconformal mechanics extended by the odd integral $`\psi _3`$ might also be constructed in an obvious way. Having in mind the correspondence $`\alpha ^2𝒥`$, $`\mathrm{\Sigma }\mathrm{\Gamma }\frac{1}{3}Q_S`$, $`\alpha \mathrm{\Gamma }Q_Y`$, $`\alpha \mathrm{\Sigma }𝒬_L`$ and relations (3.22), one finds that the even nilpotent quantities $`i\mathrm{\Gamma }Q_2`$, $`i\alpha \mathrm{\Gamma }Q_1`$, $`i\mathrm{\Gamma }\stackrel{~}{Q}_2`$ and $`i\alpha \mathrm{\Gamma }\stackrel{~}{Q}_1`$ would be the analogs of the integrals $`𝒬_P`$, $`𝒬_𝒫`$, $`𝒬_X`$ and $`𝒬_𝒳`$, respectively, which, with taking into account Eq. (2.7), would generate the nonlinear Poisson bracket relations of the form presented in the Table. One could treat the complete set of these classical ‘commutation’ relations of the all even and odd integrals as some nonlinear Poisson superalgebra $`𝒢`$ . However, its nature is essentially different from that of the nonlinear generalization of the $`osp(2|2)su(2)`$ generated by the integrals $`H`$, $`K`$, $`D`$, $`𝒬_L`$, $`Q_P`$, $`Q_X`$, $`Q_𝒫`$, $`Q_𝒳`$ and $`J_i`$ (plus the Yano supercharge $`Q_Y`$  being the classical analog of the grading operator of the quantum version of this superalgebra, see below). The difference is that the nonlinearity of the generalized $`osp(2|2)su(2)`$ is encoded in the central charge $`𝒥`$ appearing additively and multiplicatively in the Poisson bracket relations, while the nontrivial $`so(1,2)`$ generators $`H`$, $`D`$ and $`K`$ appear as multiplicative factors in the Poisson superalgebra $`𝒢`$. One of the consequences of this is that there exists no analog of the rescaling procedure (3.22) which would transform $`𝒢`$ into some Lie superalgebra.

The role of the quantum $`osp(2|2)`$ spin operator is played by

$$\widehat{𝒬}_L=\frac{\mathrm{}}{2}\left(\widehat{L}_i\sigma _i+\mathrm{}\right).$$
(3.24)
In correspondence with the classical Poisson bracket relations, it rotates the supercharges (cf. with the two last relations from (2.4)),

$`[\widehat{𝒬}_L,\widehat{Q}_X]=i\mathrm{}\widehat{Q}_𝒳,[\widehat{𝒬}_L,\widehat{Q}_P]=i\mathrm{}\widehat{Q}_𝒫,`$
$`[\widehat{𝒬}_L,\widehat{Q}_𝒳]=i\mathrm{}\widehat{𝒥}\widehat{Q}_X,[\widehat{𝒬}_L,\widehat{Q}_𝒫]=i\mathrm{}\widehat{𝒥}\widehat{Q}_P.`$ (3.25)
Here

$$\widehat{𝒥}=\widehat{J}_i^2\nu ^2+\frac{1}{4}\mathrm{}^2$$

is the quantum analog of (3.6) with the quantized $`\nu `$, $`|\nu |=\mathrm{}n/2`$, $`n`$, and the quantum analogs of $`Q_𝒳`$ and $`Q_𝒫`$ are obtained from (3.17), (3.18) by a simple antisymmetrization of the noncommuting factors $`\widehat{L}_j`$ and $`\widehat{P}_k`$, or $`\widehat{L}_j`$ and $`\widehat{X}_k`$.

The only difference of the nonlinear superalgebra formed by the fermion-monopole integrals of motion in comparison with the quantum version of the $`osp(2|2)`$ superalgebra (2.4) consists in the presence of the additional factor $`\widehat{𝒥}`$ in commutators (3.25) and in anticommutators of $`\widehat{Q}_𝒫`$ and $`\widehat{Q}_𝒳`$ (see the table). In accordance with the classical Poisson bracket relations we have also

$$[\widehat{Q}_P,\widehat{Q}_𝒳]__+=[\widehat{Q}_𝒫,\widehat{Q}_X]__+=\mathrm{}(\widehat{𝒬}_L+\widehat{𝒥}).$$

The integral $`\widehat{𝒬}_L`$ commutes with all the even generators of the nonlinear generalization of the $`osp(2|2)su(2)`$, and in addition, due to the relation

$$\widehat{𝒬}_L=\sqrt{\frac{\mathrm{}}{2}}\widehat{Q}_Y$$
(3.26)
anticommutes with the odd supercharges. Satisfying the relation

$$\widehat{𝒬}_L^2=\frac{\mathrm{}^2}{4}\widehat{𝒥},$$
(3.27)
it is the square root from the central element $`\widehat{𝒥}`$ of the nonlinear superalgebra, and may be treated simultaneously as the grading operator of the nonlinear version of the $`osp(2|2)su(2)`$.

The quantum analog of the classical relation (3.5) is

$$\widehat{C}=4\widehat{D}^22(\widehat{K}\widehat{H}+\widehat{H}\widehat{K})+\widehat{𝒥}2\widehat{𝒬}_L=\frac{3}{4}\mathrm{}^2.$$

This quantum relation fixing the value of $`\widehat{C}`$ (cf. with (2.12)) appears as the condition of existence of nontrivial solutions to the system of homogeneous equations being the quantum analog of (3.21).

In representation where the squared full angular momentum operator is diagonal, $`\widehat{J}_i^2=j(j+1)\mathrm{}^2`$, $`j+\frac{1}{2}=\mathrm{}^1|\nu |+m`$, $`m=0,1,2,\mathrm{}`$, we have $`\widehat{𝒥}=(|\nu |+m)^2\nu ^2`$ . Then, in accordance with relation (3.27), for the states with $`m>0`$ the appropriately normalized operators $`\widehat{𝒬}_L`$, $`\widehat{Q}_𝒳`$ and $`\widehat{Q}_𝒫`$ (see eq. (3.22)) together with the rest of integrals of motion generate the Lie superalgebra $`osp(2|2)su(2)`$. However, as in the case of the Kepler problem, such a normalization procedure has a hidden nonlocal nature. Following ref. , one can show that in the sector $`m=0`$, corresponding classically to the phase space surface given by the equations $`L_i=0`$, $`S_jn_j=0`$, the symmetry of the system is reduced to the conformal symmetry $`so(1,2)`$.

Note that the analogy with the Kepler problem, mentioned in the Introduction, is given by the quantum relations (3.27),

$$[\widehat{Q}_P,\widehat{Q}_P]__+=2\mathrm{}\widehat{H},[\widehat{𝒬}_L,\widehat{Q}_P]=i\mathrm{}\widehat{Q}_𝒫,[\widehat{Q}_𝒫,\widehat{Q}_𝒫]__+=2\mathrm{}\widehat{𝒥}\widehat{H},$$
(3.28)
see Eq. (3.25) and the Table. Here, however, it is necessary to stress that the relation (3.27) is satisfied by the $`\widehat{𝒬}_L`$ not as by the even generator of the nonlinear superconformal algebra, but as its grading operator which coincides (up to the quantum factor, see Eq. (3.26)) with the Yano supercharge $`\widehat{Q}_Y`$ .

## 4 Discussion and outlook

To conclude, let us summarize the obtained results and discuss shortly some problems that deserve a further attention.

Comparing the system of the charged fermion in the field of the Dirac magnetic monopole with the model of superconformal mechanics, we have showed that its integrals of motion generate a nonlinear $`_2`$-graded Poisson algebra, or quantum super- algebra, which may be treated as a nonlinear generalization of the $`osp(2|2)su(2)`$. In this nonlinear superalgebra, containing the $`osp(1|2)`$  as a Lie sub-superalgebra, the shifted square of the full angular momentum of the system plays the role of the central charge appearing additively and multiplicatively in the quantum (anti)commutation and classical Poisson bracket relations. The square root from the central charge is the $`osp(2|2)`$ spin generating the $`u(1)`$ rotations of the odd supercharges. Classically, it has an odd counterpart, whose quantum analog is, up to a numerical factor $`\sqrt{\mathrm{}/2}`$, the same $`osp(2|2)`$ spin operator. As an odd integral, it generates a nonlinear supersymmetry discussed earlier in . Since it anticommutes with all other odd supercharges, and commutes with all the even integrals of the nonlinearly generalized $`osp(2|2)su(2)`$ (including itself), it may be identified as a grading operator of the superalgebra. Note also that the form of the nonlinear superalgebra can be simplified a little bit by shifting the $`osp(2|2)`$ spin for the central charge, $`𝒬_L𝒬_L+𝒥\mathrm{\Lambda }`$ (see the table).

The natural question is what are the possible physical consequences of the described nonlinear superconformal symmetry of the charge-monopole system? Having in mind the mentioned analogy with the hidden symmetry of the Kepler problem, it would be interesting to look at the charge-monopole scattering problem  from the perspective of the revealed symmetry.

In refs.  it was observed that the change of a boson-fermion coupling constant $`\alpha n\alpha `$, $`n`$, in the superconformal mechanics model corresponds to the change of the particle’s spin $`\mathrm{}/2`$ for $`n\mathrm{}/2`$, and that the modified superconformal model is characterized by the nonlinear superconformal symmetry $`osp(2|2)_n`$, in which the set of $`2(n+1)`$ odd integrals constitute the spin-$`\frac{n}{2}`$ representation of the $`so(1,2)`$ . Proceeding from the close similarity between the fermion-monopole system and superconformal mechanics model, one could expect the appearance of some generalization of the nonlinear superconformal symmetry $`osp(2|2)_n`$ of refs.  as a symmetry for a higher spin charged particle in the field of the Dirac monopole.

Acknowledgements

The work has been supported in part by CONICYT-Chile (CL), and by FONDECYT-Chile (grant 1010073) and by DICYT-USACH (MP).


format: text

text:
# Dynamical Motifs: Building Blocks of Complex Network Dynamics

## Abstract

Spatio-temporal network dynamics is an emergent property of many complex systems which remains poorly understood. We suggest a new approach to its study based on the analysis of dynamical motifs – small subnetworks with periodic and chaotic dynamics. We simulate randomly connected neural networks and, with increasing density of connections, observe the transition from quiescence to periodic and chaotic dynamics. We explain this transition by the appearance of dynamical motifs in the structure of these networks. We also observe domination of periodic dynamics in simulations of spatially distributed networks with local connectivity and explain it by absence of chaotic and presence of periodic motifs in their structure.

Dynamics in networks underlie functioning of many complex systems such as the brain Koch and Laurent (1999), cellular regulatory machinery Goldbeter (2002), ecosystems Kondoh (2003) and many others. These systems exhibit a wide repertoire of dynamics, ranging from periodic oscillations in cell cycle and brain rhythms to chaos in food webs and chemical reactions. Despite the recent rapid advancements in our ability to elucidate statistical properties of the underlying networks Albert and Barabasi (2002); Dorogovtsev and Mendes (2002); Newman (2003), surprisingly little is understood about their dynamical behavior. This is due to several reasons, in particular, inadequacy of the methods of nonequilibrium statistical mechanics in the domain of heterogeneous mesoscopic systems and inability of the dynamical systems theory to deal with systems having more than order-1 dimensions.

Fundamental problem which one faces while trying to understand dynamics in complex networks is the strong influence of their structure on their non-Hamiltonian dynamics. This influence may induce long term connectivity-dependent spatio-temporal correlations which present formidable problem for understanding of the dynamics. Statistical methods allow to solve this problem in the limit of infinite-size networks Sompolinsky et al. (1988), but they are not applicable to the study of realistic networks with non-uniform connectivity and a relatively small size.

It was recently found that many real networks include statistically significant subnetworks, so-called motifs, in their structure Milo et al. (2002). In this Letter we suggest the use of dynamical motifs – small subnetworks with non-trivial dynamics – as a new approach to the study of recurrent dynamics in complex networks. In it we combine dynamical and statistical methods to identify dynamical motifs and evaluate probability of their occurrence in the structure of networks. We show that the emergence of periodic and chaotic dynamics in networks of increasing structural complexity is linked to the appearance of periodic and chaotic motifs in their connectivity. We also consider spatially distributed networks with local connectivity and show that chaotic motifs are absent in their structure. We also suggest that this approach may be useful for study of the dynamics in networks of arbitrary structure and size.

In many complex systems the dynamics of individual elements and the rules of their interaction are relatively simple and the resulting complex behavior is an emergent consequence of these interactions. Hence, in order to study the influence of the structure on the dynamics of networks let us focus on models with simplest interactions and dynamics at each node. Let $`x_i(t)[0;1]`$, $`i=1,\mathrm{},N`$ be a set of variables describing properly scaled states of $`N`$ elements connected in a network. Consider the time evolution of network’s state vector $`𝑿(t)=\{x_1(t),x_2(t),\mathrm{},x_N(t)\}`$ described by the following set of first order differential equations

$$\frac{d𝑿(t)}{dt}=𝑿(t)+𝑭(𝑿(t)),$$
(1)
where $`𝑭(𝑿)=\{f_1(𝑿),f_2(𝑿),\mathrm{},f_N(𝑿)\}`$ is a set of sigmoid nonlinearities with $`[0;1]`$ value ranges. This general class of models includes continuous version of Random Boolean (Genetic) Networks (cRBN) Mestl et al. (1997); Glass and Hill (1998), in which $`f_i(𝑿)`$ are randomly chosen Boolean functions of their arguments, and continuous-time Artificial Neural Networks (cANN) Hopfield (1984), in which $`f_i(𝑿)=f((\widehat{W}𝑿)_i+\sigma _i)`$, where $`\widehat{W}`$ is the coupling matrix and $`\sigma _i`$ are thresholds. Both of these models were shown to exhibit complex periodic and chaotic dynamics in the biologically relevant cases of intermediate probabilities of gene expression in cRBN Glass and Hill (1998) and non-symmetric interactions in cANN Sompolinsky et al. (1988).

To illustrate the use of dynamical motifs we employ a simple cANN model with $`f(x)=(1+\mathrm{exp}(20x))^1`$, uniform external excitation $`\sigma _i=\sigma =0.5`$ and inhibitory interactions of the same strength: $`\widehat{W}=\widehat{G}w`$, where $`w=5`$ and $`\widehat{G}`$ is the adjacency matrix of the directed graph on which the network is defined. In this setting the model is similar to the simplified version of a balanced network model vanVreeswijk and Sompolinsky (1996) with excitatory connections replaced by a uniform field and can be viewed as a simple model of a cortical microcircuit. It is also an extension of the concept of winnerless competitive networks Rabinovich et al. (2001) to the case of arbitrary connectivity. However, methods presented in this Letter can be used for other models as well.

We have performed Monte Carlo simulations of the described above cANN model defined on an ensemble of random networks with $`N=200`$ nodes and uniform probability $`p`$ of node-to-node connections, i.e., an Erdős-Rényi (ER) ensemble. A sample of $`210^4p`$ random networks was generated for each considered $`p`$ and cANN dynamics was simulated 100 times on each of the networks, each time starting with different initial condition taken at random from the hypercube $`R_{(0;1)}^{200}`$. Sets of initial conditions were considered in order to eliminate the influence of the basins of attraction in multistable networks which in itself is a complicated issue requiring separate research. Largest Lyapunov exponent $`\lambda `$ was calculated in each simulation. Networks with at least one initial condition leading to $`\lambda (0.005;0.005)`$, typically $`\lambda 10^4`$ were classified as having limit cycle dynamics and with $`\lambda >0.005`$, typically $`\lambda 10^1`$ as having chaotic dynamics. As the probability of connections $`p`$ was increased, the transition from fixed point to periodic and chaotic dynamics was observed around $`p=0.015`$ (Fig. 1, triangles). The transition to solely chaotic dynamics occurred around $`p=0.025`$ (Fig. 1, squares).

We now apply the concept of dynamical motifs in order to explain such observations and make further predictions about the dynamics in networks. The main idea behind this approach is that the transition to periodic or chaotic overall dynamics in a network occurs due to the appearance in its structure of small, not necessary isolated, subnetworks which have the same type of dynamics. We call these subnetworks dynamical motifs. Of course many dynamical motifs may be present in a given dynamical network, but at least one is needed in order for the network to have a given type of dynamics. The dynamical phase transitions that are observed in models of complex networks are then identified with the percolations of dynamical motifs, i.e., $`0`$-to-$`1`$ transitions in the probability of their occurrence.

Let us consider an ER network with the probability of node-to-node connection $`p`$. The probability $`p_n`$ that some $`n`$ nodes of this network form a given motif with $`l`$ links and no self-loops is equal to $`p^l(1p)^{n(n1)l}`$. It is possible that some of the nodes in the motif are suppressed by connections from a number $`f`$ of nodes outside of a motif that are frozen in the $`\mathrm{"}+1\mathrm{"}`$ state. Such connections would suppress dynamics of the motif and should be ruled out. By excluding them we obtain corrected probability

$$p_{nf}=p^l(1p)^{n(n+f1)l}.$$
(2)
It is difficult to calculate exactly the probability to find $`N_{(n;l)}`$ such motifs in a network. However, approximate calculation of the probability $`P_{(n;l)}`$ to encounter one or more motifs is straight forward and is expected to work well in the case of sparsely connected networks ($`p<<1`$):

$`P_{(n;l)}`$ $`=`$ $`1p(N_{(n;l)}=0)1(1p_{nf})^{\frac{N!}{A(Nn)!}}`$ (3)
$``$ $`1\mathrm{exp}\left({\displaystyle \frac{p_{nf}N!}{A(Nn)!}}\right),`$
where $`N!/(A(Nn)!)`$ is the number of ways to pick $`n`$ nodes of the motif from the $`N`$-node network multiplied by $`n!/A`$ – number of ways to label a motif, with $`A`$ being the order of motif’s automorphism group. This formula predicts percolation of these motifs at some intermediate value of $`p`$ which depends on $`n`$ and $`l`$. We are interested in the values of $`n`$ and $`l`$ for which the percolation occurs at the smallest $`p=p_c`$. Let us define it by the point where $`P_{(n;l)}=1/2`$. Then

$$\frac{N!}{(Nn)!A}p_c^l(1p_c)^{n(n+f1)l}=\mathrm{log}2.$$
(4)
Assuming $`Nn`$ and $`p_c1`$ we find that $`p_cA^{1/l}N^{n/l}`$. To minimize $`p_c`$, $`n/l`$ should be maximized and hence subnetworks with most nodes and least links will appear first as $`p`$ is increased from $`0`$.

Subnetworks with limit cycle dynamics include 3-loop (Fig. 2(a)), 4-loop and other, more complicated, structures. Since for the $`n`$-loop $`l=n`$ and $`A=n`$, 3-loop has smallest $`p_c`$. According to (3), its probability of occurrence is given by

$$P_{(3;3)}1\mathrm{exp}\left(\frac{N^3}{3}p^3(1p)^{3(1+f)}\right)$$
(5)
and is plotted in Fig. 1 by a dashed line (with $`f`$ evaluated from simulations). This estimate predicts the appearance of dynamics in ER networks very accurately.

In order to find chaotic motifs we used the nauty package McKay (1998) to generate all possible non-isomorphic directed graphs with up to 8 nodes and 11 links, simulated the cANN dynamics on them and calculated the largest Lyapunov exponent $`\lambda `$ for each. Digraphs with $`\lambda >0.005`$, typically $`\lambda 10^1`$ were classified as chaotic. In Fig. 2(b-d) we show the first three chaotic motifs in the order of increasing number of nodes (5, 6 and 7 nodes) and minimal number of links (9, 10 and 10 links). Also, we found six non-isomorphic chaotic motifs with 8 nodes and 11 links, four of them with $`A=2`$ and two with $`A=1`$. Numerical evaluations of $`p_c`$ according to (4) indicate that the latter motifs have smallest $`p_c0.025`$. Probability to find one or more such motifs in an ER network is given by

$$P_{(8;11)}1\mathrm{exp}\left(4N^8p^{11}(1p)^{45+8f}\right)$$
(6)
and is piloted in Fig. 1 by a solid line (with $`f`$ evaluated from simulations of chaotic networks). As can be seen from the plot, this prediction is reasonably good. The discrepancy may be caused by the approximate nature of the estimate (3), severe undersampling of the network space in simulations and disregard of the fact that not only frozen, but also periodically oscillating external nodes suppress chaos in these motifs.

While the origin of periodic dynamics in $`n`$-loops is obvious as they merely are negative feedback loops, the nature of chaos in chaotic motifs is not self-evident. We have traced the route to chaos in the first chaotic motif by lowering $`w`$ to $`0.5`$ and then gradually increasing it. In Fig. 3 the bifurcation diagram of the local maxima of $`x_1(t)`$ oscillations is plotted. This diagram reveals two period doubling cascades, one starting around $`w=0.7`$ and another one around $`w=2.5`$.

However, there are no conclusive experimental observations of chaotic dynamics in either genetic or neuronal networks. Presence of chaotic dynamics would be inconsistent with the requirements of robustness and reproducibility of the response imposed on the living organisms by the environment. On the other hand, periodic dynamics in these networks are very common. Hence, some of the assumptions that were used in these simplified models must be wrong. As we show below, one of them is the assumption of uniformly random connectivity. Recent experimental data suggests that metabolic networks possess scale-free structure Jeong et al. (2000) while neuronal networks are highly clustered on both small Shefi et al. (2002) and large Hilgetag et al. (2000) spatial scales. Moreover, neurons in the brain frequently form ordered spatial structures with distance-dependent probabilities of connections, so-called cortical microcircuits Silberberg et al. (2002); Maass et al. (2002).

To illustrate the influence of spatial structure on the dynamical properties of networks we simulated the cANN model on the 12-by-12 two-dimensional square lattice with neuron-to-neuron connection probabilities obeying Gaussian distribution and forbidden self-connections:

$$p(d_{ij})=KN(1\delta _{ij})e^{\left(\frac{d_{ij}}{\gamma }\right)^2}/\underset{m,n=1}{\overset{N}{}}(1\delta _{mn})e^{\left(\frac{d_{mn}}{\gamma }\right)^2}$$
(7)
where $`d_{ij}`$ is a metric distance between neurons $`i`$ and $`j`$, $`\gamma `$ is the length scale of the distribution, $`K`$ is the average number of connections per neuron and $`\delta _{ij}`$ is the Kronecker delta. In effect, $`\gamma `$ controls clustering of the connectivity, with values close to $`1`$ corresponding to networks with mostly local connectivity and large values effectively diminishing the role of spatial structure and corresponding to ER-like connectivity.

We generated a random sample of 1000 such networks with $`\gamma =2`$ and $`K=14`$. As in the case of an ER sample, cANN dynamics was simulated in each of the networks for 100 different random initial conditions and the largest Lyapunov exponent was calculated in each simulation. An average connectivity $`K=14`$ corresponds to $`p0.1`$ which has led to approximately $`99\%`$ of chaotic networks in a sample of ER ensemble (Fig. 1(b)). On the contrary, around $`99\%`$ of the networks with $`\gamma =2`$ exhibited periodic dynamics and only about $`1\%`$ were chaotic. This result indicates that clustering plays an important role in defining dynamical properties of neural networks. It may support an observation that many real neuronal networks are locally clustered and exhibit reproducible, except for stochastic effects, dynamics.

We now show how the idea of dynamical motifs may be used to understand these observations. Let us enumerate grid nodes by $`1,\mathrm{},N`$ and consider a motif with $`n`$ nodes and $`l`$ links placed on the grid. We label its nodes by $`i_1,i_2,\mathrm{},i_n`$ and its links by $`i_{a_1}i_{b_1}`$, $`i_{a_2}i_{b_2}`$, …, $`i_{a_l}i_{b_l}`$ with $`a_jb_j`$, $`j=i\mathrm{}l`$ denoting ordered pairs of nodes that are connected. Probability $`P_{i_ai_b}`$ for the grid nodes $`i_a`$ and $`i_b`$ to be connected is distance-dependent and is given by (7). Then the average probability that $`n`$ nodes of a network form this motif is obtained by averaging over all possible placements of its nodes on a grid:

$$p_n\frac{1}{N^n}\underset{i_1,\mathrm{},i_n=1}{\overset{N}{}}\left(\underset{j=1}{\overset{l}{}}P_{i_{a_j}i_{b_j}}\underset{k=1}{\overset{s}{}}(1P_{i_{u_k}i_{v_k}})\right),$$
(8)
where $`s=n(n1)l`$ and $`u_kv_k`$ are all the pairs of unconnected nodes. For example, an average probability for a 3-loop (Fig. 2(a)) is $`p_3=\frac{1}{N^3}_{i_1,i_2,i_3=1}^NP_{i_1i_2}P_{i_2i_3}P_{i_3i_1}(1P_{i_2i_1})(1P_{i_3i_2})(1P_{i_1i_3}).`$ As expected, in the limit of distance-independent probabilities expression (8) becomes equivalent to the ER case. Probability of occurrence of one or more motifs in a network can again be approximated by (3). It is approximately 1 for 3- and 4-loops and $`P_m0`$ for the (5; 9) motif in networks with $`\lambda =2`$. Other chaotic motifs would be even less probable because connection probability falls off quickly with distance in these networks. Also, $`P_m1`$ for the (5; 9) motif in networks with $`\lambda =12`$. Hence, periodic motifs are present and chaotic motifs are absent in spatial networks with local connectivity ($`\lambda =2`$), but chaotic motifs are present in non-local networks with $`\lambda =12`$. These calculations may also explain recent observations of periodic and chaotic dynamics in models of cortical neural microcircuits with local and non-local spatial organization of connectivity Maass et al. (2002). Eq. (8) may also be applied in the study of networks with other distributions of connectivity.

In conclusion, a method to study dynamical behavior of networks by examining minimal building blocks of the dynamics was suggested. Calculations of abundance of dynamical motifs in networks with different structure allow to study and control dynamics in these networks by choosing connectivity that maximizes the probability of motifs with desirable dynamics and minimizes probability of motifs with unacceptable dynamics. Using this method we predict that connectivity of cortical microcircuits might be such that it minimizes the occurrence of chaotic motifs in their structure.

It was shown in Milo et al. (2002) that many real networks have 3-loops in their structure. In most cases there are very few of such loops and it was argued that their presence is not statistically significant. However, we suggest that such dynamical motifs are important because presence of even one or two of them may profoundly influence dynamical behavior of the whole network by slaving dynamics of many adjacent nodes.

###### Acknowledgements.

The author would like to thank Ramon Huerta, Mikhail Rabinovich, Michael Cross and Dmitri Chklovskii for usefull discussions, Brendan McKay for extending his nauty package with digraphs and Gilles Laurent for continuous inspiration and support. This work was partially supported by NSF grants EIA-0130708 and EIA-0130746 and DOE grant DE-FG03-96ER14592.


text:
# 1 Introduction

## 1 Introduction

We have developed the program DIANA (DIagram ANAlyser), which allows to calculate Feynman diagrams as ‘input’ for further formulae manipulating languages (mainly FORM ) ,  (see also http://www.physik.uni-bielefeld.de/`~`tentukov/diana.html). Meanwhile there exists a series of applications , which would not have been possible without DIANA.

The problem is that in order to cope with the high precision experiments of present-day high energy accelerators, the corresponding calculations within the ‘Standard Model’ (SM) of elementary particle physics must be of similar precision. This means, e.g., for 1-loop approximations even for $`22`$ processes the calculation of the order of several hundred diagrams. This number increases rapidly with the number of external legs and/or the number of loops such that one is easily forced to calculate a number of diagrams of the order of thousands. For this one needs an automation to generate the diagrams and this is what DIANA does.

Having produced the FORM ‘input’ for each of the diagrams, in a next step the execution of the FORM program has to run for each diagram separately and the analytic result of all the separate calculations has to be summed up. In many cases like e.g. 1-loop $`22`$ calculations the execution time of the FORM jobs is still relatively short and one can just run the corresponding jobs one after the other (e.g. in terms of ‘folders’). In more complicated cases, however, not only the number of diagrams increases but also the analytic calculation of the single diagrams gets more and more time consuming. Here it pays to distribute the essentially independent calculations of the separate diagrams over different computers. In the project described here we have extended DIANA to be able to perform this task and we give detailed hints for potential users of how to apply it.

The program DIANA, written in C, contains two ingredients:

1. Analyzer of diagrams.
2. Interpreter of a special text manipulating (TM) language.

The analyzer reads QGRAF  output and passes the necessary information to the interpreter. For each diagram the interpreter performs the TM program, producing input for further evaluation (e.g. by means of FORM) of the diagram. The TM language is a TeX-like language. The main goal of the language is the creation of text files.

Similar to the TeX language, each command has to begin with an escape (“$`\backslash `$”) character. All lines without escape - characters are simply typed to the output file. Some of the TM commands are built-in TM operators while some are user-defined functions (returning a value) written in the TM language itself.

The main goal of parallel processing is to reduce wall-clock time111The elapsed time between start and finish of a process. which is the users waiting time. Parallelism doesn’t come for free; always it has some overhead with respect to serial execution, but it can significantly reduce the wall-clock time.

Not every problem can be divided into parallel tasks. An example of a parallelizable problem is the multiplication of two matrices. An example of a non-parallelizable problem is the calculation of the Fibonacci series (1,1,2,3,5,…) by means of the formula $`F(k+2)=F(k+1)+F(k)`$.

Computations in perturbative Quantum Field Theory involve the calculation of Feynman diagrams. DIANA is used to produce the input for their further analytic evaluation. In fact DIANA needs a “model file” produced by the user and then generates the “input” in terms of formally defined vertices and propagators and of coupling parameters . This generation of Feynman diagrams itself is not a good parallelizable problem. Moreover, the time DIANA spends to produce such input is negligible with respect to the time used for the diagram evaluation. Thus the present approach consists in generating input for each diagram sequentially, with the possibility to parallelize the further evaluation.

After the diagrams are generated, DIANA may be used as a “control center” for further evaluations (in parallel) by invoking the corresponding programs and providing them the generated input. To avoid a cluster/processor overloading, each time only one job per node/processor is actually running while all the rest is queued. Such an approach is known as a Batch Queueing System (BQS). There exist a lot of such systems, both free and commercial . Usually, these systems are aimed to deal with a big number of different isolated tasks, while in our case we have a huge number of nearly even tasks.

There are two kinds of optimization of BQS available. The first is for the case when the average number of jobs is much larger than the number of nodes. In this case BQS usually provides various complicated methods for scheduling, message pasting, job run-time quotas and resource management in order to distribute computational resources among various tasks of all kinds. In our case all these mechanisms are not needed. Secondly, if the average number of jobs is comparable with the number of nodes, which is typical for parallel computation, a BQS should provide load balancing, process migration mechanisms and some others.

Compared to that, DIANA has to implement parallelism in terms of job queueing, and the typical situation consists of a long queue of nearly even tasks with the same priority. Evidently, we need not any load balancing. Indeed, the best procedure is to send a new task to a node immediately when the node becomes free. Thus, the real problem in our case is the problem of synchronization. Traditionally, this problem is ignored in BQS since all jobs are assumed to be completely independent. The synchronization problem arises in true parallel systems. Since we use queueing in order to implement a parallelism, the problem is of immediate interest in our case.

The TM language contains several groups of operators permitting DIANA to make a fine co-operation with the underlying operational system (UNIX). The operators `\system()` and `\asksystem()` execute an external command synchronously (see sect. 2), i.e. they wait for the command to be completed. The operator `\pipe()` (sect. 3) starts the external command opening an input-output channel for it, and can be used in order to extend DIANA in the spirit of a component model (sect. 3.4). The term “component model” (see, e.g., ) means that a software system is built from “components”. Components are high level aggregations of smaller software pieces, and provide a “black box” building block approach to software construction.

Let us now suppose that we use a cluster with disk space shared by means of NFS222Network File System, and all results must be collected into one resulting file `log.all`, while every job produces a file `log.#` where `#` is the order number of the job. Since jobs are running and completing independently of each other, we can only collect all `log.#` into `log.all` after all the jobs are finished. This leads to producing a lot of files `log.#` at an intermediate step, which can overload a file system.

The simple solution is to allow some of the newly started jobs to be synchronized with all previously started jobs. Indeed, in this case after each job we can start another “slave” job, which appends the `log.#` file containing the result of the “master” job to the file `log.all`. To obtain a correct order of the file `log.all`, this copying job must be performed only after all earlier jobs are finished.

Another problem with cluster computations is that the optimal placement of the resulting file `log.#` is usually a `/tmp` directory which is local with regard to the current node, on which the job “number `#`” is performed. But to do this, the “slave” copying job has to “stick” to the “master” job, i.e. it must be performed on the same node as the “master” job.

Both above mentioned problems are solved by means of so-called job attributes, see sect. 4.2.

Yet another problem is the transaction problem, which in our case means whether a job group should be restarted on failure, and what the failure/success conditions are. Sometimes it is necessary to perform some complicated job with many unreliable intermediate steps (e.g., breakdown of some connection) and at the end return the exit code depending on the status of the whole transaction. In such cases it is useful to have a possibility to restart the job many times. But for conventional jobs consisting of one external program the number of restarts must not be too large in order to permit the user to kill jobs which failed.

Conditions on which a job is assumed to have failed may be rather complicated, too. For example, the above mentioned copying “slave” job is just a quick system command “cp”. The probability of its failure is very low, less then the probability of some network connection failure during the commands initiation. If started, such a job, most probably, will be completed successfully independently of the DIANA client/server status. That is why it is reasonable to assume that the job is successful if it is started by the server. On the other hand, the “master” job is expected to return some exit code, but not to be killed by some signal. For the solution of these problems see sect. 4.2 as well.

The operator `\_exec()` and companions can be used to define several macros and TM functions in order to create a BQS which meets our requirements; for a simplified example see sect. 4.4. There is the possibility to build a really powerful BQS based on the `\_exec()` family combined with external components communicating with DIANA through the operator `\pipe()`. A simplified version of this is demonstrated.

## 2 Running external commands

The operator `\system(command)` executes the external `command` and returns the exit code. Usually, 0 means that the invoked program was executed successfully. Example: `\system(ls)` types to the screen the content of the current directory and returns 0.

The operator `\asksystem(command,text)` executes the external `command`, using the second argument as its “standard input”. It reads the first line of the external command output and stores it. Then the external command is terminated, and the stored line is returned. For example, `\asksystem(cat,Hello!)` returns the text “Hello!”, but `\asksystem(cat,One!\eol()Two!)` returns the text “One!” (`\eol()` is the DIANA command ending the line).

Another example:

```
\offleadingspaces
  * Host: \asksystem(hostname,); \asksystem(date,)

```

in the TM program has led to the following line in the produced output:

```
* Host: phya24; Fri May  30 22:51:38 CET 2003

```

## 3 Dialog with an external program

### 3.1 Starting a pipe

The operator `\asksystem()` is used to “ask” a single question from the command, as described above. In order to organize a dialog with an external program, the operator `\pipe(command)` can be used. It starts the `command`, swallowing its standard input and output. It returns an integer number, a PID333Process IDentifier of a newly started process, or an empty string, if it fails. Further, the returned PID can be used in order to send some text to the program, or to read program output.

After the operator `\pipe()` returns the control to the TM program, the program initiated by `command` continues to run. Its standard input and output references are stored by DIANA. Both input and output are not connected with any terminal device. The running external program is visible from the TM program as a duplex “pipe” identified by the PID of the external program.

The operator `\closepipe(rpipe)` (here `rpipe` is the PID of the external program returned by `\pipe()`) terminates the external program. It closes the programs’ IO channels, sends to the program a KILL signal and waits for the `command` to be finished.

### 3.2 Reading and writting with the pipe

There are two operators to write to the pipe. One is `\topipe(rpipe,text)`, and another is `\linetopipe(rpipe,text)`. The latter appends a new line symbol to the text placed into the pipe while the former sends `text` to the pipe as it is. The necessity of two operators comes from the fact that most of interactive programs have line-oriented input/output. The program reads from the terminal a whole line and will not continue until the line is completed. On the other hand, sometimes it is necessary to use character-oriented input/output.

The corresponding reading operators are `\frompipe(rpipe)` and `\linefrompipe(rpipe)`. The operator `\linefrompipe()` reads from the pipe and returns a whole line. The operator is fast, but it is aimed to read only lines. In contrast, the operator `\frompipe()` can be used in order to read parts of lines. It stops reading if the line is completed, at an end-of-file condition or if there are no more data available in the pipe. The operator `\frompipe()` reads from the pipe character-by-character, therefore it is much slower then the operator `\linefrompipe()`444The operator $`\backslash `$linefrompipe() makes bufferred reading. It reads some block from the pipe, and then returns the part of the block corresponding the first whole line. After the operator is performed, some piece of the text corresponding to the beginning of the next line is also transferred from the pipe into an internal buffer..

It is not allowed to mix `\frompipe()` and `\linefrompipe()`. The result may be unpredictable and probably not what one expects.

These operators may be used to deal with the DIANA standard input/output. If the first argument, `rpipe`, is $`0`$, the operators `\topipe(rpipe,text)` and `\linetopipe(rpipe,text)` will output their second argument to the terminal. The same with `\frompipe()` and `\linefrompipe()`: if their arguments are $`0`$, these operators read from the keyboard.

### 3.3 Related operators

The operators `\frompipe()` and `\linefrompipe()` block the TM program until some data will be available from the pipe. Sometimes this is not acceptable. In order to solve this problem, the user can apply the operator `\ispipeready(rpipe)` (is-pipe-ready). The operator returns `ok` if there are data available for the `\frompipe()` operator. If `\ispipeready()` returns an empty string, the operator `\frompipe()` invoked afterwards will block the TM program and wait for some data to be available.

The operator `\ispipeready()` may be used only in combination with `\frompipe()`. The operator `\linefrompipe()` may still return some text immediately even if the operator `\ispipeready()` has returned an empty string.

The operator `\checkpipe(rpipe,signum)` sends the signal “`signum`” (an integer number) to the external program initiated by `\pipe()`. If the signal is delivered successfully, the operator returns `ok`. If the signal cannot be delivered, e.g. if the external program was terminated, then the operator returns an empty string. If the first argument, `rpipe`, is $`0`$, the operator does nothing and returns `ok` since DIANA assumes that the user checks the standard input/output. If the second argument, `signum`, is $`<1`$, it is assumed to be 0. It must be an integer number, symbolic names are not accepted. The primary purpose of the operator is to send the signal 0 to the pipe: this signal will not affect the program but all checking will be performed.

### 3.4 Extension of DIANA by means of external components

The operator `\pipe()` can be used to add some functionality to DIANA in the spirit of a component model (see Introduction).

Let us suppose that we need to deal with high precision arithmetic. Under UNIX, there exists the command “`dc`” – a standard desk calculator which supports unlimited precision arithmetic. It reads arguments from the standard input as so-called “reverse-polish notation”555Reverse Polish Notation is an arithmetic formula notation, introduced in 1920 by the Polish mathematician Jan Lukasiewicz. In this notation, the operands precede the operators, thus dispensing the need of parentheses. For example, the expression 3 * ( 4 + 7) would be written as 3 4 7 + \*.  and types the answer to the standard output.

The following function `\fdiv(a,b)` returns the quotient `a`/`b` with 10 fraction digits:

```
\function fdiv a,b;\modesave()\-
   \if not exist"_dc"then
      \if"\export(_dc,\pipe(dc))"eq""then
         \killexp(_dc)
         \moderestore()\return()
      \endif
      \linetopipe(\import(_dc),\(10 k))
   \endif
   \let(a,\tr(-,_,\get(a)))
   \let(b,\tr(-,_,\get(b)))
   \linetopipe(\import(_dc),\(c )\get(a)\( )\get(b)\( / p))
   \moderestore()\return(\linefrompipe(\import(_dc)))
\end

```

This is a very simple demo version, it is non-optimal and does not contain exception handling.

First, if `dc` is not running, the function starts `dc`, swallowing its input-output channels (it assumes that the external program `dc` is started if the global variable `_dc` is defined). Then it sets the precision 10, sending the line “`10 k`” to `dc`.

It replaces possible signs “`-`” in both `a` and `b` by the symbol “`_`”: the input `dc` language requires negative numbers to be preceded by “`_`”; the sign “`-`” cannot be used for this, since it is a binary operator for subtraction.

Then the function sends the line “`c |a| |b| / p`” to the running `dc` command. The calculator clears previous results (command `c`), evaluates the quotient and puts the result to the standard output (command `p`).

In this example it is possible to use the operator
`\asksystem(dc, 10 k |a| |b| / p)`
instead:

```
\function fdiv a,b;\modesave()\-
   \let(a,\tr(-,_,\get(a)))
   \let(b,\tr(-,_,\get(b)))
   \moderestore()\return(
     \asksystem(dc, \(10 k )\get(a)\( )\get(b)\( / p))
   )
\end

```

For each call of `\fdiv(a,b)` it would start `dc`, evaluate and return the result. The time consumed by such a function will be about 100 times larger than the variant with `\pipe()`, but it is possible in principle.

Another example illustrates the “real” dialog with the component used to organize some simple GUI666Graphical User Interface. Let’s suppose some Tcl/Tk777A popular scripting language intended primarily for creating GUI, see http://www.tcl.tk/scripting script is placed into the executable file `guiDemo` (see appendix A; this example is available at
http://www.physik.uni-bielefeld.de/`~`component\_model.tar.gz).

This small “widget” with two buttons, “Run/Stop” and “Quit” represents a simple dialog (see Fig. 1). Every time the user clicks the “Run/Stop” checkbutton, the script types to the standard output 0 or 1 (supposed to be swallowed by DIANA), depending on the state of the button, and reads the window header from the standard input. If the user clicks the “Quit” button, then the script outputs the line `Quit` to the standard output, and exits.

The script is started by means of the operator `\pipe(./guiDemo)` during initialization of a TM program:

```
\Begin(initialization)
   . . .
   \export(guiDemo,\pipe(./guiDemo))
   \topipe(\import(guiDemo),Start/Quit?\eol())
   \if"\frompipe(\import(guiDemo))"ne"1"then
      \exit(-1)
   \endif
   \topipe(\import(guiDemo),Run\( )0...\eol())
\End(initialization)

```

At this point the window appears with the title “Start/Quit?” (Fig. 1 a)) , and the execution of the TM program will be suspended since it is blocked while waiting for the data from the pipe.

If the user clicks on the “Quit” button, the TM program will be finished. If the user switches on the “Run/Stop” button, the TM program starts to run (Fig. 1 b)).

Each time the user clicks one of the buttons (or closes the window), the script emits some text, which becomes available for `\frompipe()`.

In the beginning of the “`regular`” section there is the following TM code:

```
\section(regular)

\if"\ispipeready(\import(guiDemo))"eq"ok"then
\beginlabels
\label(_start)
\goto(_\frompipe(\import(guiDemo)))
\label(_0)
\topipe(\import(guiDemo),Stop\( )\currentdiagramnumber()\eol())
\goto(_start)
\label(_)
\label(_Quit)
\exit(-1)
\label(_1)
\topipe(\import(guiDemo),Run\( )\currentdiagramnumber()...\eol())
\endlabels
\endif

```

If the user switches off the “Run/Stop” button, this code suspends the execution of the TM program (Fig. 1 c)). The number of the current diagram will be typed into the title.

The user can continue (checking the “Run/Stop” button), or interrupt the TM program by means of the “Quit” button.

## 4 Running external commands asynchronously

### 4.1 Parallelization, local and remote jobs and synchronization

The operator `\system()` executes commands synchronously, i.e. it waits for them to be completed and returns an exit code. In contrast, the operator `\_exec()` executes commands in the background888On UNIX, the background jobs are programs which are executing in such a way that they return the shell prompt while they continue to operate. Here we use the term “background” in a more general sense.. Similar to the operator `\pipe()`, it does not wait for the command to be completed. It returns an empty string on success, or some diagnostics on failure. This operator may be used to parallelyze the evaluation of a process by running more than one job simultaneously.

All jobs started by the operator `\_exec()` are running independently of the TM program invoking them. To synchronize the TM program with all these jobs, there is an operator `\_waitall()`. It suspends execution of the TM program until timeout is expired, or until all jobs started by the `\_exec()` operator are completed (for further options see Sect. 4.3). It returns the number of jobs which are not yet finished, or an empty string, if there are no jobs anymore. The single argument of the operator `\_waitall()` is a timeout in milliseconds. E.g., `\_waitall(1000)` will return in one second the number of remaining jobs. If the user wants to know how many jobs are not yet finished, he may use the operator `\_waitall(0)`.

To avoid overloading of a processor, by default at each time only one job is actually running while all the rest is waiting in the queue. The operator `\_exec()` just queues jobs.

On SMP999Symmetric MultiProcessing computers, the optimal number of simultaneously running jobs is the number of processors. This number can be changed by means of the option `-smp`. Thus, `-smp 8` tells DIANA to run on the computer 8 jobs simultaneously while all the rest is queued.

In case of a cluster of computers with a current directory shared by means of NFS e.g., the operator `\_exec()` can use DIANA servers running on other computers. To run DIANA as a server, the user may use one of the following two options: the option `-s` tells DIANA to run a server listening to some port, and the option `-d` forces DIANA to fork out a “daemon” running in the background and listening to the port instead of DIANA. Thus, each computer on which the user has executed the command (possibly automized, see macro `STARTSERVERS` below)

```
diana -d 1 -q

```

becomes available to perform the commands queued by the operator `\_exec()` (we assume that the current directory is shared by NFS among all computers in the cluster). Here `-d 1` tells DIANA to run a daemon accepting only one connection, and the option `-q` terminates the father DIANA process. For SMP computers the optimal argument for the `-d` (or `-s`) option is the number of processors.

Running jobs are controlled by means of “handlers”. These can be understood as communication channels between running jobs and DIANA. Their number is the highest possible number of simultaneously running jobs. By default, the operator `\_exec()` will give priority to local handlers, i.e. if the two possibilities occur simultaneously to run a job locally or on a remote server, the job will be started on the local computer. When DIANA starts a new job, it tries to use one of the free handlers with minimal nice. The nice is an integer number which is set for each handler. By default, the local handler has nice 0, while the remote handler has nice 1.

The nice of local handlers can be set by an optional parameter for the option `-smp`, separated by a comma from the mandatory parameter. Thus, `-smp 8` tells DIANA to run on the computer 8 jobs simultaneously with nice 0 while `-smp 8,2` tells DIANA to run these 8 jobs with nice 2.

The same with the remote server: `-d 2` (or `-s 2`) tells DIANA to run a daemon (server) accepting two connections with nice 1, and `-d 2,0` (or `-s 2,0`) tells DIANA to run a daemon (server) accepting two connections with nice 0.

### 4.2 Job attributes and exact syntax of operators

Two operators `\_exec()` and `_waitall()` permit the user to organize a simple parallel session for evaluations on SMP computers and/or clusters of independent computers with shared disk space. But very often this is not enough (see Introduction). Therefore, each job started by the operator `\_exec()` must have further attributes (for a complete list see the end of the present section). The first one is the “sync” attribute; if it is set, the job will be started to run only after all previously started jobs are completed. The second attribute is the “sticky” attribute. This attribute requires a parameter, which gives reference to the “master” job to which the “slave” (getting this parameter) has to stick. If this attribute is set, the “slave” will be performed on the same node as the “master” job was running.

If the “master” job fails before the “sticky” “slave” job was started, the latter will fail too if a third attribute is set; otherwise it will be performed independently of the result of the “master” job. Let’s call this attribute “stickyfail”.

There are some other attributes, which will be explained further down. The total number of attributes is 32, but at present many of them are merely reserved for future developments.

The operator `\_execattr(attr,param)` is used to change default job attributes. `attr` is a string of length 32 in general. The position of each character corresponds to one of the attributes. The first character corresponds to the “sync” attribute, the second one to the “sticky” attribute, etc. If the corresponding character is 0, then the attribute is cleared, if 1, the attribute is set; any other character means that the attribute will not be changed. If the string `attr` is longer than 32, all extra characters will be ignored. If it is shorter, all remaining attributes will not be changed. Examples:

```
\_execattr(00000000000000000000000000000000,)

```

clears all attributes.

```
\_execattr(1,)

```

sets the “sync” attribute.

The second argument, `param`, is used to attach a parameter to attributes which require it. Parameters are attached consecutively only to those attributes which require them and only to attributes which are set. If more than one parameter is specified, they have to be separated by the end-of-file symbol (EOF), which can be obtained by the operator `\eof()`. If less parameters than set attributes are specified, they will be cycled over all set attributes requiring a parameter.

Each job started by `\_exec()` has a unique name, provided by the user (see below) or defined automatically. The parameter for sticky attributes is the name of the “master” job. It is not allowed to stick to jobs which are not yet queued. The name of the last queued job can be obtained by the operator `\lastjobname()`. So, the operator

```
\_execattr(!10,\lastjobname())

```

does not change the “sync” attribute, raises the “sticky” attribute to stick the new job to the job queued just before, and clears the “stickyfail” attribute.

Another example:

```
\_execattr(111,\lastjobname())

```

The newly created job will be executed firstly after the “master” job and all previously queued jobs are finished, secondly, on the same node101010DIANA assumes the “node” to be the IP address of a server, so the conception of “nodes” is actually supported only for clusters. For SMP, the whole computer is assumed to be a single node. on which the “master” job was performed, and thirdly only if the “master” job was successful.

If the parameter for the “sticky” attribute is an empty string, the last job name will be used and the above example is equivalent to

```
\_execattr(111,).

```

The operator `\_exec()` queues jobs defined by commands with arbitrary number of command line arguments. The command and the arguments must be pushed into a stack in natural order by means of the operator `\push()`. E.g., in order to execute a command “`ls -l`”, the user has to prepare the stack by means of the following set of operators:

```
\push(\eof())
\push(ls)
\push(-l)

```

and then invokes the operator `\_exec()`. The command line arguments appear in the stack in reverse order, reading from top to bottom, i.e. in the stack the EOF is situated on the bottom. The `\_exec()` operator reverses the command line arguments from the stack such that they appear in natural order again. The exact syntax of the `\_exec()` operator is as follows:

```
\_exec(name, attr, param).

```

Here `name` is the unique job name. If it is left empty, which is recommended in general, it will be assigned automatically.

The second and third argument have the same meaning as described above in connection with the `\_execattr()` operator. Here they are considered as local arguments and the default ones are not overwritten by the `\_exec()`.

Besides these most important attributes we describe two more useful ones. They are “successcondition” and “restart”.

If the job is sent to a server, DIANA waits for an answer from it. The server reports success/failure of starting the job, and after the job is completed, the server reports the status of the job returned by the system.

By default, the job is assumed to be successful if the server reports the status. However, sometimes it is useful to investigate the status returned by the system, or assume that the job is successful if it is started by the server (see the discussion in the Introduction).

The “successcondition” attribute (the fourth one) can accept a parameter which can take the following values:

* -2 – the job is successful if it is started by the server;
* -1 – the same like without the attribute. The job is successful if the server reports the status returned by the system.
* from 0 to 255 – the job is successful if the external program initiated by the job has been completed and returned the exit code less or equal to the specified number.

Another problem with success/failure conditions is the question how many times the job should be restarted when it fails. By default, the job is not restarted at all on failure. To change this behaviour, a fifth attribute can be set. We call it the “restart” attribute. The corresponding parameter is the number of restarts, which must be an unsigned integer from 0 to 255.

Here is the synopsis of all attributes actually used by DIANA for the time being:

| No | Attribute | Parameter |
| --- | --- | --- |
| 1 | sync |  |
| 2 | sticky | job name (text) |
| 3 | stickyfail |  |
| 4 | successcondition | -2…255 |
| 5 | restart | 0…255 |

### 4.3 Related operators

As described in Sect. 4.1, the operator `\_waitall()` returns control if there are no more running jobs or if the timeout is expired. As third possibility the operator will return control if some data are available on a definite pipe. This pipe must be set by means of the operator `\setpipeforwait(rpipe)`, where `rpipe` is the PID returned by the operator `\pipe()`, or 0. In the latter case the operator `\_waitall()` will return control if there is something typed on the keyboard.

If control is returned due to available data from the pipe, the number returned by the operator `\_waitall()` is preceded by a minus sign. If all jobs finish simultaneously with data occurring in the pipe only a minus sign is returned.

The operator `\getpipeforwait()` returns the PID of the pipe which has been set by `\setpipeforwait(rpipe)` or an empty string if there is no active pipe for `\_waitall()`.

`\pingServer(ip)` checks if a DIANA server is available on a given IP address. The argument `ip` is the IP address in standard dot notation. The operator returns `alive` if the server responds, or an empty string if the server cannot be found or does not respond.

`\killServer(ip)` kills the DIANA server running on the specified IP address. The argument `ip` is again the IP address in standard dot notation. The operator returns `ok` on success, or an empty string on failure.

`\killServers()` kills all running DIANA servers. It returns an empty string on success, or `none` on failure.

`\lastjobname()` returns the name of the last job started by the operator `\_exec()`.

`\lastjobnumber()` returns the number of the last job started by the operator `\_exec()`.

`\whichIP(jobname)` returns the IP address as 8 hexadecimal digits or an empty string on failure.

`\whichPID(jobname)` returns the PID as a hexadecimal number or an empty string on failure.

`\getnametostick(jobname)` returns the name of the “master” job to which the specified “sticky” job `jobname` has to stick. On failure it returns an empty string.

`\jobtime(jobname)` returns 8 hexadecimal digits, the job running time in milliseconds. If the job is not yet running, the operator returns “00000000”.

`\jobstime(jobname)` returns 8 hexadecimal digits, the job starting time in milliseconds. The starting time is counted from the moment of the DIANA job queuing mechanism being activated till the time the job starts to run. If the job is not yet started, it returns “00000000”.

`\jobftime(jobname)` returns 8 hexadecimal digits, the job finishing time in milliseconds. The finishing time is counted from the moment of the DIANA job queuing mechanism being activated till the job is completed. If the job is not yet finished, it returns “00000000”.

`\rmjob(jobname)` removes the named job. If the job is running, the related external programs will automatically be killed by the signal SIGKILL. The operator returns an empty string independently of the result.

`\clearjobs()` clears all jobs. It returns an empty string on success, or the string “Client is dead.”

`\jobstatus(jobname)` returns the status of a specified job. The status is given in terms of 8 hexadecimal digits. The first two digits stand for the `exit()` argument of the external program if the program exited normally, otherwise they are “00”. The third and fourth digits are the following: “00” – normal exit, “01” – exit because of non-caught signal, “02” – the job was not run, “03” – no such job, “04” – job is finished, but its status is lost (often occurs after the debugger being detached); otherwise – “ff”. If the job was removed by the operator `\rmjob()`, the third digit will not be “0” but “1”.

The last 4 digits stand for the number of the signal that caused the external program to terminate if the fourth digit was “1”, otherwise “0000”.

`\startjobtimeout(timeout)` sets the timeout for attempts to start jobs (milliseconds). After the timeout is expired and the job is not yet running, it will be moved to another handler if the total number of the timeout hits is less then 10. If the number of timeout hits is 10, the job fails. Time is counted from the moment of the job being sent to the remote (or local) server. The operator returns the previous value of the timeout or an empty string on failure.

`\gconnecttimeout()` sets the timeout for the connection with a remote server (milliseconds). It returns the previous value of the timeout, or an empty string on failure.

`\jobhits(jobname)` returns 6 hexadecimal digits. The first two digits stand for the number of times the job was restarted due to the start timeout expiration. The third and fourth digits stand for the number of times the job was restarted after failures and the last two digits represent the current placement of the job: “01” – the job is in the main queue, “02” – the job is in the synchronous queue, “03” – the job is finished, “04” – the job failed, “05” – the job runs, “06” – the job is ready to run111111I.e. all conditions to start the job are fulfilled and the job will be started as soon as some proper handler becomes available. as a non-sticky job, “07” – the job is ready to run as a sticky job.

`\failedN()` returns number of failed jobs, or an empty string, on failure.

`\hex2sig(sig)` converts DIANA’s internal signals’ hexadecimal representation to local system ones (decimal numbers).

`\sendsig(jobname,signal)` sends a signal to the external program which was initiated by the specified job. Note, the signal will be sent to all external programs initiated by the job121212The external program initiated by the job runs in a new session (UNIX - specific term). Actually, the signal will be sent to the process group corresponding to the initial external program.. It expects that the `signal` is either a symbolic name SIG… (the SIG prefix may be omitted), or a number. All possible symbolic names are (a subset from the conventional UNIX signal identifiers): SIGHUP SIGINT SIGQUIT SIGILL SIGABRT SIGFPE SIGKILL SIGSEGV SIGPIPE SIGALRM SIGTERM SIGUSR1 SIGUSR2 SIGCHLD SIGCONT SIGSTOP SIGTSTP SIGTTIN SIGTTOU SIGBUS SIGPOLL SIGPROF SIGSYS SIGTRAP SIGURG SIGVTALRM SIGXCPU SIGXFSZ SIGIOT SIGEMT SIGSTKFLT SIGIO SIGCLD SIGPWR SIGINFO SIGLOST SIGWINCH. If the signal is specified by a number, the signal will be sent as it is. If the signal is specified by a symbolic name, DIANA will convert it into an internal representation transferred to the remote server. This may be useful if the numerical representation of signals on the remote system differs from the local one. The operator returns an empty string on success; on failure it returns: “10” – job is not run, “20” – can’t read a signal from DIANA; less then 10: “01” – an invalid signal was specified, “02” – the pid or process group does not exist, “03” – the process does not have permission to send the signal, “04” – unknown error.

`\getJobInfo(jobn, format)` returns information about the job number `jobn`, formatted according to `format`. The latter is a string of type `n1/w1:...:nn/wn’`, where `n#` is a field number and `w#` is its width. If `w#`$`>0`$, the text in the field will be right justified and padded on the left with blanks. If `w#`$`<0`$, then the text in the field will be left justified and padded on the right with blanks. If `w#`=0, then the width of the field will be of the text length. Here is a complete list of all available fields:

1. current placement, see above;
2. return code, 8 hexadecimal digits, see above;
3. IP address (in dot notation);
4. PID (decimal number);
5. attributes (decimal integer);
6. timeout hits (decimal number), see above;
7. fail hits (decimal number), see above;
8. max fail hits (decimal number), see above;
9. errorlevel (decimal number), see above;
10. the job name;
11. number of command line arguments;
12. all command line arguments starting from a second one (spaces separated);
13. all command line arguments starting from a third one (spaces separated);
14. all command line arguments starting from a fourth one (spaces separated).

If `n#` is zero or negative its absolute value is interpreted as the position of a single command line argument.

Example: `\getJobInfo(1, 4/10:3/15)` returns the PID of the external program of the first job and the IP address of the computer on which the job runs. PID will be returned as a decimal number padded by spaces on the left to fit a field of width 10, and IP will be returned in dot notation padded by spaces on the left to fit a field of width 15.

`\tracejobson(filename)` starts jobs tracing (for details see
http://www.physik.uni-bielefeld.de/`~`tentukov/parallel\_demo.tar.gz) into files (“filename.var” and “filename.nam”), returns an empty string.

`\tracejobsoff()` ceases tracing. It returns an empty string. After it has stopped, tracing cannot be continued until all jobs are cleared by means of the operator `\clearjobs()`.

### 4.4 Example of high-level usage of parallel processing facilities

Very often the external program may run in a subshell as a conventional UNIX command. For such cases the following high-level TM function `\exec(command)` can be defined:

```
\function exec cmd;
 \push(\eof())
 \push(sh)
 \push(-c)
 \push(\get(cmd))
 \return(\_exec(,00011,255\eof()4))
\end

```

The function starts the job consisting of some (maybe composed) standard UNIX command. The job will be successful if the command returns some exit code (under UNIX there is no possibility to have an exit code higher then 255). On failure the job will be restarted up to four times (the number 4 after `\eof()`).

The function `\stick(command)`:

```
\function stick cmd;
 \push(\eof())
 \push(sh)
 \push(-c)
 \push(\get(cmd))
 \return(\_exec(,11110,\eof()-2))
\end

```

performs the command `cmd` only after all earlier jobs are completed (the first 1 of the second argument of `\exec()`). This function in general is used to collect all produced files. That is why it performs `cmd` on the same computer as the preceding job (the second 1; since the job name to stick to is an empty string, the last job name will be used). The job started by this function is successful if it is started by the server (the fourth 1, and the corresponding parameter is “-2”). The job will not be restarted on failure (the last 0).

The function `\wait(timeout)`:

```
\function wait to;
 \while"\let(r,\_waitall(\get(to)))"ne""do
  \message(\get(r)\( jobs are not finished))
 \loop
\end

```

suspends execution of the TM program until all jobs are completed. Each “`timeout`” milliseconds the function reports the number of jobs which are not yet finished.

These three functions can be used to organize a simple parallel session with proper synchronization. As an example, let us consider the following script `runf`, which is used to run FORM jobs in parallel after the FORM input has been produced in a folder (see , p. 158):

```
#!diana -smp 1 -c runpar.tml
\STARTSERVERS(phya25,phya26,phya27,phya28)
\system(echo > log.all)

\REPEAT(N)
\exec(form -d i=\get(N) do.frm > /tmp/log.\get(N))
\stick(cat /tmp/log.\get(N) >> log.all)
\stick(rm /tmp/log.\get(N))
\ENDREPEAT()

\wait(2000)

```

The user enters: `runf 186 200` , and the system executes:
`diana -smp 1 -c runpar.tml runf 186 200`.

The file `runpar.tml` (see Appendix B) contains definitions of various TM functions and some settings; in particular it redefines the comment character as `#`. The following is the structure of the file `runpar.tml`:

```
messages disable
esc character = \
comment character = #
output file =""
debug off
only interpret
\begin translate

```

Definitions various functions and macros, in particular `\exec()``\wait()`,
`\REPEAT()`, `\ENDREPEAT()` and `\STARTSERVERS()`

```
\program
\-
\SET(_CMDLN)(\CMDLINE(1))
\RMARG(1)
\{\include(\GET(_CMDLN))\-
\setout(null)
\}
\end translate

```

The main program switches off the output (by means of the directive `\-`), switches off “hash” regime for arguments by means of the directive “`\{`” (see below), stores the first command line argument (“`\SET(_CMDLN)(\CMDLINE(1))`”), removes it (“`\RMARG(1)`”) and includes the file the name of which is the first command line argument
(“`\include(\GET(_CMDLN))`”).

By default, DIANA provides for the function and operator arguments some special “hash” regime: all spaces and ends of line are ignored. The directive “`\{`” cancels this regime, the directive “`\}`” activates it again. Without this directive all commands with spaces must be quoted by the quotation operator “`\()`” which is not convenient for a script.

The macro `\STARTSERVERS(list)` checks if each server from `list` is working and if not starts the server by means of the `ssh`. For example, for the host phya26 the following command will be performed:

```
ssh phya26 cd CD ; diana -d 1 -q

```

where “`CD`” is a current directory, e.g. `/home/user/jobs`.

The operator `\system(echo > log.all)` is used to produce an empty file “`log.all`”.

All the instructions between `\REPEAT(N)` `...` `\ENDREPEAT()` are cycled with `N=186,...,200`. We assume that there is some folder file, say, `tt.in` with FORM input for each diagram. The FORM program `do.frm` evaluates a diagram by virtue of including a fold from the folder `tt.in` via an instruction like `#include tt.in # n’i’`. The macro definition `i` comes from the command line `form -d i=\get(N) do.frm`, where `\get(N)` runs from 186 to 200. Each FORM job saves the result to the local directory, but the corresponding concatenation is performed by `\stick(cat ...)` on the same computer. At the end, all results will be collected in the file `log.all`, and all intermediate files `\tmp\log.#` will be removed.

After all jobs are queued, the function `\waitall(2000)` will report every 2 seconds how many jobs are not yet completed.

This example is available at
http://www.physik.uni-bielefeld.de/`~`tentukov/parallel\_demo.tar.gz.

In the archive there are two directories: demo1 and demo2. The example is situated in demo1; see the Readme file for details of installation. For a more realistic (and complicated) example containing jobs controlling and monitoring facilities see demo2.

## Acknowlegement

M. Tentukov is grateful for financial suuport by the DFG under project no. FL 241/4-2

## Appendix

## Appendix A The listing of the Tcl/Tk script guiDemo

The following Tcl/Tk script is supposed to be placed into the executable file `guiDemo`:

```
#! /bin/sh
#\
exec wish "$0" "$@" -geometry +200+300

# catches destroy window event:
wm protocol .WM_DELETE_WINDOW {puts "Quit";exit 0}

label .title
pack .title

# create relief canvas:
frame .buttons -bd 10 -relief raised

#Button "Run/Stop":
global checkb
frame .buttons.run
checkbutton .buttons.run.run -text "Run/Stop"\
  -command {puts "$checkb"; flush stdout;\
            .title configure -text [gets stdin]}\
             -variable checkb
pack .buttons.run.run
pack .buttons.run -side left

#Button "Quit"
frame .buttons.quit
button .buttons.quit.quit -text "Quit" -command\
  {puts "Quit";exit 0}
pack .buttons.quit.quit
pack .buttons.quit -side left
pack .buttons

# Read initial header:
.title configure -text [gets stdin]
#End:

```

The script creates a window with two buttons. The check button “Run/Stop” has two states, “selected” and “deselected”. The global variable `checkb` is set to indicate whether or not this button is selected. Every time the user clicks the “Run/Stop” checkbutton, the script types to the standard output the value of `checkb` and reads the window header from the standard input. The “Quit” button, when pressed, outputs the line “`Quit`” to the standard output and exits from the script. The same occurs when the user closes the window.

## Appendix B The listing of the file “runpar.tml”

The following listing is typed in typewriter while comments are typed using italic.

```
Preamble:
messages disable
esc character = \
comment character = #
output file =""
debug off
only interpret
\begin translate

The function returns  true if
the argument is a number:
\function isnumber str;
  \if"\get(str)"eq""then
     \let(res,)
  \else
     \let(sk,\getcheck())
     \setcheck(0123456789)
     \let(res,\check(\get(str)))
     \setcheck(\get(sk))
  \endif
  \return(\get(res))
\end

\function wait to;
 \while"\let(r,\_waitall(\get(to)))"ne""do
  \message(\get(r)\( jobs are not finished))
 \loop
\end

Begin macrodefinition of the
REPEAT environment
\DEF(REPEAT)
\IFSET(__REP)
\ERROR(Nested REPEAT!)
\ENDIF
\SET(__REP)(1)

Checking command line arguments:
\if"\exist(__From)"eq"false"then
   \let(__From,\cmdline(1))
\endif
\if"\exist(__To)"eq"false"then
   \let(__To,\cmdline(2))
\endif
\beginlabels
\label(again)
\while"\isnumber(\get(__From))"ne"true"do
   \let(__From,\read(’\get(__From)’
      \( is not an integer, enter new FROM:)))
\loop

\while"\isnumber(\get(__To))"ne"true"do
   \let(__To,\read(’\get(__To)’
      \( is not an integer, enter new TO:)))
\loop

\if"\numcmp(\get(__From),\get(__To))"eq">"then
   \message(\get(__From)>\get(__To)!)
   \let(__From,)\let(__To,)
   \goto(again)
\endif
\endlabels

 Pre-processor SCAN is used since macro argument \#(1)
 cannot be used in \if operator:
\SCAN(\if"\#(1)"eq""then)
   \let(_iND,_index) Default iterator
\else
   \let(_iND,\#(1)) Use argument as iterator
\endif

\let(\get(_iND),\get(__From))
\do  Start the main loop
\ENDDEF
End macrodefinition of the
REPEAT environment

Macrodefinition of the ENDREPEAT
environment, rather simple:
\DEF(ENDREPEAT)
End of the main loop
\while"\numcmp(\inc(\get(_iND),1),\get(__To))"ne">"loop
\UNSET(__REP)
\ENDDEF

\function exec cmd;
   \push(\eof())
   \push(sh)
   \push(-c)
   \push(\get(cmd))
  \return(\_exec(,00011,255\eof()4))
\end

\function stick cmd;
   \push(\eof())
   \push(sh)
   \push(-c)
   \push(\get(cmd))
   \return(\_exec(,11110,\eof()-2))
\end

Attention! The following macro assumes that
the executable file “diana” is availavle
from the system path set in the PATH variable,
and the current directory is shared by NFS:
\DEF(STARTSERVERS)
   \let(_cmd,\( ’cd )\asksystem(pwd,)\( ; diana -m d -d 1,1 -q’))
   \FOR(_srv)(\*) Loop on all arguments
     Remove possible spaces from the server name:
     \let(_n,\delete(\_srv(),\( )))
     \let(_ip,)
     \if"\get(_n)"ne""then
        Get IP address:
        \let(_ip,\getip(\get(_n)))
     \endif
     \if"\get(_ip)"ne""then
        Is the server alive?:
        \if"\pingServer(\get(_ip))"eq""then
           Not yet. Start it:
           \message(\(Starting server at )\get(_ip)...)
           \system(\(ssh )\get(_ip)\get(_cmd))
        \endif
     \endif
   \ENDFOR
  Servers may be started successfully, but
   network connection establishing may take some time.
   So try to ping servers, and if it does not respond,
   wait one second:
   \FOR(_srv)(\*)
     \let(_n,\delete(\_srv(),\( )))
     \let(_ip,)
     \if"\get(_n)"ne""then
        \let(_ip,\getip(\get(_n)))
     \endif
     \if"\get(_ip)"ne""then
        \if"\pingServer(\get(_ip))"eq""then
           \system(sleep 1)
        \endif
     \endif
   \ENDFOR
\ENDDEF

Main program:
\program
\- Switch off output
Store first command line argument:
\SET(_CMDLN)(\CMDLINE(1))
\RMARG(1)\ Remove it
Now command line arguments available
from the script are counted in correct order
Include a script body:
\{\include(\GET(_CMDLN))\-
Switch off output and close output
possibly opened by the script:
\setout(null)
\}
\killServers() Kill all servers
\end translate

```