Keywords

1 Introduction

Physical swarms, which solve corporative task, are widely used in different branches of human activity, industrial and mobile robotics, concurrent computation, control systems, etc. [1,2,3,4,5]. Such systems include number of units, each of which operates accordingly to its own algorithm realized on Von Neumann type controllers. Due to consecutive interpretation of algorithm operators and accidental character of data processed, runtime of controller is a random value, and outcome of program operation is stochastic [6]. So for proper operation, when solving a corporative task, swarm should be tuned in such a way, that corporative algorithm should be divided on pieces, which are realized on swarm units, and interpretation of algorithm pieces should be carried out in the proper sequence [7]. Such alignment is called synchronization. For optimal synchronization adequate model of parallel process should be worked out. Below approach to simulation, based on Petri-Markov nets [8], which from one side permits to evaluate random time intervals characteristics, and from other side take into account interaction of parallel processes, is used. Also for optimal synchronization it is necessary to have criterion, which permits to evaluate effectiveness of corporative algorithm division. Below universal criterion, called distributed forfeit, is proposed, and formulae for effectiveness estimation with use proposed criterion are obtained.

Approaches to simulation of synchronized operation of swarm are currently known insufficiently, that explains necessity and relevance of the investigations in this domain.

2 Petri-Markov Model of Synchronized Operation

Operation of swarm, which includes M units and solves some corporative task, may be described with use Petri-Markov net (PMN) apparatus [8]. Swarm operation model is as follows (Fig. 1).

Fig. 1.
figure 1

Petri-Markov network describing the synchronous operation of equipment.

Full size image
$$ \Pi = \left\{ {{\text{A}},{\text{Z}},\upiota\left( {\text{Z}} \right),{\text{o}}\left( {\text{Z}} \right)} \right\}, $$
(1)

where \( {\text{A}} = \left\{ {{\text{A}}_{1} , \ldots ,{\text{A}}_{j} , \ldots ,{\text{A}}_{J} } \right\} \) is the set op places, which describes operation of M swarm units; \( {\text{Z}} = \left\{ {{\text{Z}}_{1} , \ldots ,{\text{Z}}_{j} , \ldots ,{\text{Z}}_{J} } \right\} \) is the set of transitions, which describes synchronization procedures; \( \upiota\left( {\text{Z}} \right) \) \( {\text{o}}\left( {\text{Z}} \right) \) are input and output functions of transitions, correspondingly; J number of operators in corporative algorithm of swarm behavior when solving corporative task;

$$ {\text{A}}_{j} = \left\{ {\upalpha_{j,0} ,\upalpha_{j,1} , \ldots ,\upalpha_{j,m} , \ldots ,\upalpha_{j,M} } \right\},\quad 1\, \le \,j\, \le \,J; $$
(2)
$$ {\text{Z}}_{j} = \left\{ {\upzeta_{j,0} ,\upzeta_{j,1} } \right\},\quad 1\, \le \,j\, \le \,J; $$
(3)
$$ \left\{ {\begin{array}{*{20}l} {\upiota\left( {\text{Z}} \right) = = \left\{ {\upiota\left( {{\text{Z}}_{1} } \right), \ldots ,\upiota\left( {{\text{Z}}_{j} } \right), \ldots ,\upiota\left( {{\text{Z}}_{J} } \right)} \right\};} \hfill \\ {\upiota\left( {{\text{Z}}_{j} } \right) = \left\{ {\upiota\left( {\upzeta_{j,0} } \right),\upiota\left( {\upzeta_{j,1} } \right)} \right\},1\, \le \,j\, \le \,J;} \hfill \\ {\upiota\left( {\upzeta_{j,0} } \right) =\upalpha_{j,0} ;} \hfill \\ {\upiota\left( {\upzeta_{j,1} } \right) = \left\{ {\upalpha_{j,1} , \ldots ,\upalpha_{j,m} , \ldots ,\upalpha_{j,M} } \right\};} \hfill \\ \end{array} } \right. $$
(4)
$$ \left\{ {\begin{array}{*{20}l} {{\text{o}}\left( {\text{Z}} \right) = = \left\{ {{\text{o}}\left( {{\text{Z}}_{1} } \right), \ldots ,{\text{o}}\left( {{\text{Z}}_{j} } \right), \ldots ,{\text{o}}\left( {{\text{Z}}_{J} } \right)} \right\};} \hfill \\ {{\text{o}}\left( {{\text{Z}}_{j} } \right) = \left\{ {{\text{o}}\left( {\upzeta_{j,0} } \right),{\text{o}}\left( {\upzeta_{j,1} } \right)} \right\},1\, \le \,j\, \le \,J;} \hfill \\ {{\text{o}}\left( {\upzeta_{j,0} } \right) = \left\{ {\upalpha_{j,1} , \ldots ,\upalpha_{j,m} , \ldots ,\upalpha_{j,M} } \right\};} \hfill \\ {{\text{o}}\left( {\upzeta_{j,1} } \right) = \left\{ {\upalpha_{1,0} , \ldots ,\upalpha_{j,0} , \ldots ,\upalpha_{J,0} } \right\}.} \hfill \\ \end{array} } \right. $$
(5)

PMN operation may be considered as sequence semi-steps, which may be done either from places to transitions, \( \left( {\upalpha_{j,0} ,\upzeta_{j,0} } \right) \), \( \left( {\upalpha_{j,m,j\left( e \right)} ,\upzeta_{j,1} } \right) \), \( 1\, \le \,j\, \le \,J \), \( 1\, \le \,m\, \le \,M \), \( 1\, \le \,j\left( e \right)\, \le \,J\left( e \right) \), or from transitions to places, \( \left( {\upzeta_{j,0} ,\upalpha_{j,m} } \right) \), \( 1\, \le \,m\, \le \,M \), \( 1\, \le \,j\, \le \,J \); \( \left( {\upzeta_{j,1} ,\upalpha_{1,0} } \right) \), …, \( \left( {\upzeta_{j,1} ,\upalpha_{l,0} } \right) \), …, \( \left( {\upzeta_{j,1} ,\upalpha_{J,0} } \right) \), \( 1\, \le \,j\, \le \,J \). For semi-step execution from places \( \upalpha_{j,0} ,\upalpha_{j,1} , \ldots ,\upalpha_{j,m} , \ldots ,\upalpha_{j,M} \) into corresponding transitions random time interval t should be spent, which begins from the moment, when semi-step was done into this place. Time intervals are determined with an accuracy to time densities \( f_{j,0} \left( t \right) \), \( f_{j,m,j\left( e \right)} \left( t \right) \), \( 1\, \le \,j\, \le \,J \), \( 1\, \le \,m\, \le \,M \), \( 1\, \le \,j\left( e \right)\, \le \,J\left( e \right) \). For semi-step execution from transition \( \upzeta_{j,0} \) simultaneously to all places \( \upalpha_{j,1} , \ldots ,\upalpha_{j,m} , \ldots ,\upalpha_{j,M} \), constituting its output function \( {\text{o}}\left( {\upzeta_{j,0} } \right) \) only semi-step \( \left( {\upalpha_{j,0} ,\upzeta_{j,0} } \right) \) should be done. For execution of one of semi-step from the transition \( \upzeta_{j,1} \), the proper \( \left( {\upalpha_{j,m,j\left( e \right)} ,\upzeta_{j,1} } \right) \) semi-steps combination to named transition must be done, due to only one direction of the set \( \left\{ {1\left( e \right), \ldots ,j\left( e \right), \ldots ,J\left( e \right)} \right\} \) may be choose for doing semi-step (Fig. 1).

In such a way, transitions \( \upzeta_{j,0} \), and \( \upzeta_{j,1} \), are the synchronized one: transition \( \upzeta_{j,0} \) in the sense that all semi-steps, included into its output function \( {\text{o}}\left( {\upzeta_{j,0} } \right) \), are executed simultaneously (synchronous start), but transition \( \upzeta_{j,1} \) in the sense, that semi-step from it would not be done until all semi-steps from places of \( \upiota\left( {\upzeta_{j,1} } \right) \) will be done.

PMN timing elements are places. Time of residence PMN at places \( \upalpha_{1,0} , \ldots ,\upalpha_{j,0} , \ldots ,\upalpha_{J,0} \) is as follows

$$ f_{j,0} \left( t \right) =\updelta\left( t \right), $$
(6)

where \( \updelta\left( t \right) \) is the Dirac δ-function.

Time of residence PMN at places \( \upalpha_{1,1} , \ldots ,\upalpha_{1,m} , \ldots ,\upalpha_{1,M} \), …, \( \upalpha_{j,1} , \ldots ,\upalpha_{j,m} , \ldots ,\upalpha_{j,M} \), …, \( \upalpha_{J,1} , \ldots ,\upalpha_{J,m} , \ldots ,\upalpha_{J,M} \) is defined as the time of wandering through semi-Markov processes [9, 10] \( \upmu_{j,m} \left( t \right) \), \( 1\, \le \,j\, \le \,J,\;1\, \le \,m\, \le \,M \), which are abstract analogues of swarm unit onboard computers operation, and are defined as follows (Fig. 2):

Fig. 2.
figure 2

Semi-Markov process \( \upmu_{j,m} \left( t \right) \)

Full size image
$$ \upmu_{j,m} = \left\{ {A_{j,m} ,\varvec{r}_{j,m} ,\varvec{h}_{j,m} \left( t \right)} \right\}, $$
(7)

where \( A_{j,m} \), \( \left| {A_{j,m} } \right| = J\left( a \right) + 1 \), is the set of states, which are abstract analogues of swarm unit onboard computer algorithm operators; \( \varvec{r}_{j,m} \) is the \( \left[ {J\left( a \right) + 1} \right] \times \left[ {J\left( a \right) + 1} \right] \) adjacency matrix, which describes links between operators; \( \varvec{h}_{j,m} \left( t \right) \) is the \( \left[ {J\left( a \right) + 1} \right] \times \left[ {J\left( a \right) + 1} \right] \) semi-Markov matrix, which define time intervals of operators interpretation;

$$ A_{j,m} = \left\{ {a_{j,m,0\left( a \right)} ,a_{j,m,1\left( a \right)} , \ldots ,a_{j,m,J\left( a \right) - J\left( e \right)} , \ldots ,a_{j,m,J\left( a \right) - J\left( e \right)} } \right\}; $$
(8)
$$ \varvec{r}_{j,m} = \left[ {r_{j,m,j\left( a \right),n\left( a \right)} } \right]; $$
(9)
$$ \varvec{h}_{j,m} \left( t \right) = \left[ {h_{j,m,j\left( a \right),n\left( a \right)} \left( t \right)} \right]. $$
(10)

The set \( A_{j,m} \) is divided onto two disjoint subsets, subset of non-absorbing states

$$ \bar{E}_{j,m} = \left\{ {a_{j,m,0\left( a \right)} ,a_{j,m,1\left( a \right)} , \ldots ,a_{j,m,j\left( a \right)} , \ldots ,a_{j,m,J\left( a \right) - J\left( e \right)} } \right\}, $$
(11)

and subset of absorbing states Ej,m.

$$ \bar{E}_{j,m} = \left\{ {a_{j,m,J\left( a \right) - J\left( e \right) + 1} ,\; \ldots ,\;a_{j,m,j\left( e \right)} ,\; \ldots ,\;a_{j,m,J\left( a \right)} } \right\}. $$
(12)

Wandering through states of semi-Markov process \( \varvec{h}_{j,m} \left( t \right) \) start at the state \( a_{j,m,0\left( a \right)} \), which is the abstract analogue of “begin” operator. States \( a_{j,m,j\left( e \right)} \in \bar{E}_{j,m} \) are the abstract analogues of “end” operators for different outcomes of algorithm operation.

Element \( h_{j,m,j\left( a \right),n\left( a \right)} \left( t \right) \in \varvec{h}_{j,m} \left( t \right) \) performs weighted time density of m-th swarm unit residence in the state \( a_{j,m,j(a)} \) when decision was made about next switch into the state \( a_{j,m,n(a)} \).

Weighted time density of the semi-Markov process \( \upmu_{j,m} \) wandering from the state \( a_{j,m,0\left( a \right)} \) till the state \( a_{j,m,J\left( a \right) - J\left( e \right) + j\left( e \right)} \in E \) is as follows:

$$ h_{j,m,j\left( e \right)} \left( t \right) = {}^{r}\varvec{I}_{0\left( a \right)} \cdot L^{ - 1} \left[ {\sum\limits_{k = 1}^{\infty } {\left\{ {L\left[ {\varvec{h}_{j,m} \left( t \right)} \right]} \right\}^{k} } } \right] \cdot {}^{c}\varvec{I}_{J\left( a \right) - J\left( e \right) + j\left( e \right)} , $$
(13)

where \( {}^{R}\varvec{I}_{0\left( a \right)} \) is the row vector of size \( \left[ {J\left( a \right) + 1} \right] \), whose \( 0\left( a \right) \)-th element is equal to one, and all other elements are equal to zeros; \( {}^{c}\varvec{I}_{J\left( a \right) - J\left( e \right) + j\left( e \right)} \) is column vector, whose \( \left[ {J\left( a \right) - J\left( e \right) + j\left( e \right)} \right] \)-th element is equal to one, and all other elements are equal to zeros; \( L\left[ \ldots \right] \) и \( L^{ - 1} \left[ \ldots \right] \) are correspondingly direct and inverse Laplace transforms.

When \( J\left( e \right) = 1 \) the algorithm simulated has the only outcome, and consequently \( h_{j,m,J\left( e \right)} \left( t \right) = f_{j,m,J\left( e \right)} \left( t \right) \). When \( J\left( e \right) > 1 \), then semi-Markov process \( \upmu_{j,m} \) gets subset E, veraciously, but the state \( a_{j,m,J\left( a \right) - J\left( e \right) + j\left( e \right)} \) it gets with probability [12]

$$ p_{j,m,j\left( e \right)} = \int\limits_{0}^{\infty } {h_{j,m,j\left( e \right)} \left( t \right)dt} . $$
(14)

Pure (non-weighted) time density, expectation and dispersion are equal, correspondingly [13]

$$ f_{j,m,j\left( e \right)} \left( t \right) = \frac{{h_{j,m,j\left( e \right)} \left( t \right)}}{{p_{j,m,j\left( e \right)} }}. $$
(15)
$$ T_{j,m,j\left( e \right)} = \int\limits_{0}^{\infty } {t \cdot f_{j,m,j\left( e \right)} \left( t \right)dt} ; $$
(16)
$$ D_{j,m,j\left( e \right)} = \int\limits_{0}^{\infty } {\left( {t - T_{{m\left(\Sigma \right),n\left(\Sigma \right)}} } \right)^{2} \cdot f_{j,m,j\left( e \right)} \left( t \right)dt} . $$
(17)

Due to \( \upmu_{j,m} \) gets subset E, veraciously,

$$ \sum\limits_{j\left( e \right) = 1\left( e \right)}^{J\left( e \right)} {p_{j,m,j\left( e \right)} } = 1. $$
(18)

3 Transformation PMN to Complex Semi-Markov Process

With use formulae (13), (14), (15) obtained, Petri-Markov sublet, circled on the Fig. 2 with dashed line, may be replaced with the single state, and so the PMN Π may be replaced with complex semi-Markov process, which describes behavior of the swarm as a whole. Circled with dashed line subset is as follows

$$ \Pi _{j} = \left\{ {{\text{A}}_{j} ,{\text{Z}}_{j} ,\upiota\left( {{\text{Z}}_{j} } \right),{\text{o}}\left( {{\text{Z}}_{j} } \right)} \right\}, $$
(19)
$$ {\text{A}}_{j} = \left\{ {\upalpha_{j,0} ,\upalpha_{j,1} , \ldots ,\upalpha_{j,m} , \ldots ,\upalpha_{j,M} } \right\}, $$
(20)
$$ \left\{ {\begin{array}{*{20}l} {{\text{Z}}_{j} = \left\{ {\upzeta_{j,0} ,\upzeta_{j,1} } \right\};} \hfill \\ {\upiota\left( {\upzeta_{j,0} } \right) =\upalpha_{j,0} ;} \hfill \\ {\upiota\left( {\upzeta_{j,1} } \right) = \left\{ {\upalpha_{j,1} , \ldots ,\upalpha_{j,m} , \ldots ,\upalpha_{j,M} } \right\};} \hfill \\ \end{array} } \right., $$
(21)
$$ \left\{ {\begin{array}{*{20}l} {{\text{o}}\left( {{\text{Z}}_{j} } \right) = \left\{ {{\text{o}}\left( {\upzeta_{j,0} } \right),{\text{o}}\left( {\upzeta_{j,1} } \right)} \right\};} \hfill \\ {{\text{o}}\left( {\upzeta_{j,0} } \right) = \left\{ {\upalpha_{j,1} , \ldots ,\upalpha_{j,m} , \ldots ,\upalpha_{j,M} } \right\};} \hfill \\ {{\text{o}}\left( {\upzeta_{j,1} } \right) = \left\{ {\upalpha_{1,0} , \ldots ,\upalpha_{j,0} , \ldots ,\upalpha_{J,0} } \right\}} \hfill \\ \end{array} } \right., $$
(22)

Semi-Markov process is as follows

$$ \upmu = \left\{ {B,\varvec{r},\varvec{h}\left( t \right)} \right\}, $$
(23)

where \( B = \left\{ {b_{1} ,\; \ldots ,\;b_{j} ,\; \ldots ,\;b_{J} } \right\} \) is the set of states, which are abstract analogues of execution by swarm the complex operation due to algorithm of swarm behavior;

\( \varvec{r} = \left[ {r_{j,n} } \right] \) is the \( J \times J \) adjacency matrix; \( \varvec{h}_{j,m} \left( t \right) = \left[ {h_{j,n} \left( t \right)} \right] \) is the \( J \times J \) semi-Markov matrix.

Let us define probabilities and time densities of switch from the complex state \( b_{j} \in B \) to the complex state \( b_{n} \in B \). Semi-steps \( \left( {\upalpha_{j,0} ,\upzeta_{j,0} } \right) \) and \( \left( {\upzeta_{j,0} ,\upalpha_{j,m} } \right) \), \( 1\, \le \,m\, \le \,M \) are executed during the time which is defined with Dirac δ-function. Semi-steps \( \left( {\upzeta_{j,1} ,\upalpha_{0,n} } \right) \), \( 1\, \le \,n\, \le \,J \) are executed after logical conditions fulfillment also during defied with Dirac δ-function time. So time of residence the complex semi-Markov process in the state \( b_{j} \) till switch to the complex state \( b_{n} \) may be defined as result of competition between ordinary semi-Markov processes \( \upmu_{j,m} \), with taking into account outcomes of getting subsets \( E_{j,m} \) states.

For definition of all possible outcomes, from indexes trios \( \left[ {j,m,j\left( e \right)} \right] \), \( 1\, \le \,m\, \le \,M \), following set may be constructed

$$ \tilde{J}_{j,m} = \left\{ {\left[ {j,m,1\left( e \right)} \right], \ldots ,\left[ {j,m,j\left( e \right)} \right], \ldots ,\left[ {j,m,J\left( e \right)} \right]} \right\},\;\;1\, \le \,m\, \le \,M. $$
(24)

Cartesian product of sets \( \tilde{J}_{j,m} \) gives all possible combinations of outcomes of swarm units operation:

$$ \begin{aligned} \tilde{J}_{j} = \coprod\limits_{m = 1}^{M} {\tilde{J}_{j,m} } = \left\{ {\left( {\left[ {j,1,1\left( e \right)} \right], \ldots ,\left[ {j,m,1\left( e \right)} \right], \ldots ,\left[ {j,M,1\left( e \right)} \right]} \right), \ldots ,} \right. \\ \left. {\left( {\left[ {j,1,j\left( e \right)} \right], \ldots ,\left[ {j,m,j\left( e \right)} \right], \ldots ,\left[ {j,M,j\left( e \right)} \right]} \right), \ldots ,\left( {\left[ {j,1,J\left( e \right)} \right], \ldots ,\left[ {j,m,J\left( e \right)} \right], \ldots ,\left[ {j,M,J\left( e \right)} \right]} \right)} \right\}; \\ \end{aligned} $$
(25)

From (25) may be selected those vectors, combination of trios of which permit to do emi-step \( \left( {\upzeta_{j,1} ,\upalpha_{n,0} } \right) \):

$$ \begin{aligned} \tilde{J}_{j} \supseteq \tilde{J}_{j\left( n \right)} = \left\{ {\left( {\left[ {j,1,i\left( {e,n} \right)} \right], \ldots ,\left[ {j,m,j\left( {e,n} \right)} \right], \ldots ,\left[ {j,M,k\left( {e,n} \right)} \right]} \right)} \right., \\ \ldots ,\left. {\left( {\left[ {j,1,l\left( {e,n} \right)} \right], \ldots ,\left[ {j,m,q\left( {e,n} \right)} \right], \ldots ,\left[ {j,M,s\left( {e,n} \right)} \right]} \right)} \right\}; \\ \end{aligned} $$
(26)
$$ \left| {\tilde{J}_{j\left( n \right)} } \right| = {\rm K}\left( n \right) $$
(27)

Probability of \( \upkappa\left( n \right) \)-th combination emergence is as follows:

$$ p_{{j,\upkappa\left( n \right)}} = \prod\limits_{m = 1}^{M} {p_{{j,m,j\left[ {e,\upkappa\left( n \right)} \right]}} } ,\;\;1 \le\upkappa\left( n \right) \le {\rm K}\left( n \right). $$
(28)

So, probability \( p_{j,n} \) of switch the complex semi-Markov process μ from \( b_{j} \) to \( b_{n} \) is equal to the sum

$$ p_{j,n} = \sum\limits_{{\upkappa\left( n \right) = 1}}^{{{\rm K}\left( n \right)}} {p_{{j\left( n \right),\upkappa\left( n \right)}} } . $$
(29)

For calculation of time density \( f_{j,n} \left( t \right) \) one should consider the competition [9, 14] on the transition \( \upzeta_{j,1} \) between ordinary semi-Markov processes \( \upmu_{j,m} \). Residence at the state \( b_{j} \) is considered as completed, when last ordinary semi-Markov process reaches its \( E_{j,m} \) state according the combination (25). This is why semi-Markov processes compete for not being the last in the competition. Time of reaching subset \( E_{j,m} \) by all M may be described with the following formula:

$$ \begin{aligned} & f_{{j,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right) = \frac{{d\prod\limits_{m = 1}^{M} {F_{{j,m,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right)} }}{dt} \\ & = \sum\limits_{m = 1}^{M} {f_{{j,m,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right)\prod\limits_{\begin{subarray}{l} i = 1, \\ i \ne m \end{subarray} }^{M} {F_{{j,i,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right)} .} \\ \end{aligned} $$
(30)

where \( f_{{j,m,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right) \) is the time density of reaching the transition \( \upzeta_{j,1} \) by m-th semi-Markov process due to \( \upkappa\left( n \right) \)-th combination; \( F_{ \ldots } \left( t \right) = \int\limits_{0}^{t} {f_{ \ldots } \left(\uptau \right)d\uptau} \) if the function of distribution of probabilities.

With taking into account combination of outcomes, weighted and pure time densities of switch from the state \( b_{j} \) to the state \( b_{n} \) are as follows:

$$ h_{j,n} \left( t \right) = \sum\limits_{{\upkappa\left( n \right) = 1}}^{{{\rm K}\left( n \right)}} {p_{{j,\upkappa\left( n \right)}} f_{{j,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right)} . $$
(31)
$$ f_{j,n} \left( t \right) = \frac{{h_{j,n} \left( t \right)}}{{p_{j,n} }}. $$
(32)

After transformation for investigation of swarm behavior investigation and calculation of wandering time intervals all possible methods of semi-Markov process analysis may be used [9,10,11,12].

4 Effectiveness of Synchronization

One of the important aspects of swarm operation organization is elimination of unproductive units downtime when corporative task is solved. Parameter, which defines effectiveness, may be any, but when investigation of relay-races, distributed forfeit is of widely used. Let us considered competition of m-th и l-th swarm units, first of which gets the transition \( \upzeta_{j,1} \) during time \( f_{{j,m,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right) \), but second - during the time \( f_{{j,l,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right) \). In the case of winning in competition the first swarm unit he waits until l-th swarm unit gets \( \upzeta_{j,1} \). Waiting time is calculated as follows [15]:

$$ f_{{j,m \to l,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right) = \frac{{\upeta\left( t \right)\int\limits_{0}^{\infty } {f_{{j,m,j\left[ {e,\upkappa\left( n \right)} \right]}} \left(\uptau \right)f_{{j,l,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( {t +\uptau} \right)d\uptau} }}{{\int\limits_{0}^{\infty } {F_{{j,m,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right)dF_{{j,l,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right)} }}, $$
(33)

where τ is an auxiliary argument; \( \upeta\left( t \right) \) is the Heaviside function.

Probability of such event, expectation and dispersion of waiting time are as follows

$$ p_{{j,m \to l,j\left[ {e,\upkappa\left( n \right)} \right]}} = \int\limits_{0}^{\infty } {F_{{j,m,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right)dF_{{j,l,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right)} ; $$
(34)
$$ T_{{j,m \to l,j\left[ {e,\upkappa\left( n \right)} \right]}} = \int\limits_{0}^{\infty } {t \cdot f_{{j,m \to l,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right)dt} ; $$
(35)
$$ D_{{j,m \to l,j\left[ {e,\upkappa\left( n \right)} \right]}} = \int\limits_{0}^{\infty } {\left[ {t - T_{{j,m \to l,j\left[ {e,\upkappa\left( n \right)} \right]}} } \right]^{2} f_{{j,m \to l,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right)dt} . $$
(36)

Every of value (34), (35), (36) may characterized those or that effectiveness aspect, but more universal is the criterion, which is defined as distributed forfeit [15] \( c_{{j,m \to l,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right) \). Forfeit, receives m-th swarm unit from the l-th swarm unit if it gets the transition \( \upzeta_{j,1} \) earlier. Latecomer pays forfeit during whole the time until he m-th swarm unit waits him. In this case weighted forfeit sum is equal to

$$ C_{{j,m \to l,j\left[ {e,\upkappa\left( n \right)} \right]}} = p_{{j,m \to l,j\left[ {e,\upkappa\left( n \right)} \right]}} \int\limits_{o}^{\infty } {c_{{j,m \to l,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right)f_{{j,m \to l,j\left[ {e,\upkappa\left( n \right)} \right]}} \left( t \right)dt} ; $$
(37)

Common forfeit sum, which m-th swarm unit receives from all other units by \( \upkappa\left( n \right) \)-th combination variant is as follows:

$$ C_{{j,m,j\left[ {e,\upkappa\left( n \right)} \right]}} = \sum\limits_{\begin{subarray}{l} l = 1, \\ l \ne m \end{subarray} }^{M} {C_{{j,m \to l,j\left[ {e,\upkappa\left( n \right)} \right]}} } . $$
(38)

Common forfeit sum, which m-th swarm unit receives from all other units in the case of further switch into state \( b_{n} \) is equal to

$$ C_{j,m,n} = \sum\limits_{{\upkappa\left( n \right) = 1}}^{{{\rm K}\left( n \right)}} {p_{{j,m,j\left[ {e,\upkappa\left( n \right)} \right]}} \cdot C_{{j,m,j\left[ {e,\upkappa\left( n \right)} \right]}} } . $$
(39)

Sum \( C_{j\left( b \right),m} \) depends on parameters of ordinary semi-Markov processes (7), and forfeit discipline. Such sum may be used as optimization criterion in the task of producing optimal swarm behavior.

5 Conclusion

Working out the model of swarm synchronized operation opens new page in parallel systems theory because it permits to link real physical parameters of hardware with structure and logics of operation oh corporative algorithm, distributed among swarm units. Algorithm splitting may be done with those or that way, but with use approach proposed, swarm program designer for every mode of splitting may evaluate main characteristics both corporative algorithm as a whole, and parts of it, realized on swarm units.

Further investigation in this area should be directed to working out an algorithm splitting optimization method, based on proposed approach to parallelization modeling and evaluation of effectiveness.

The research was supported by the Foundation for Basic Research under the project 19-47-710004 r_a.