Sorting realization of well-ordered sets based on π -calculus

Abstract

π-calculus is one of the most effective means for the modeling of the concurrent mobile system at the present stage. The paper starts with a brief introduction of π-calculus, which concerns mutual simulation, the fundamentals of mobile computing, and the concept of interaction with some basic grammars and regulations of π-calculus while the system mobility is discussed with special focuses on the relation between the referent and the mobility, and the relation between the granular size and mobility. Then the analysis goes on to discuss the sorting problems that frequently occur in modeling concurrent systems. Through the discussion of the underlying sorting algorithms based on π-calculus, five processes are established by applying such artless thoughts as “looking for the seats in the cinema” or “changing keys among a group” to do quick concurrent locating and instant sorting, so that the sorting problems of specific elements in the well-ordered sets could be solved on the basis of π-calculus. In this way, the sorting results will eventually be displayed in the specified process and conveniently help the readings of other processes.

Keywords

mobile computing sorting cinema algorithm key change algorithm

1 Introduction

Nowadays, with the rapid development of computer network and continuous application of multi-core and multi-CPU processors, people’s focus on calculation has been shifted from the previous sequential computation to present concurrent mobile computation. As is known to all, however, one of the prerequisites for the computer to solve a problem is that the problem could be described with unambiguous formalization, which makes the traditional “function” theory no longer suitable for such kind of concurrent mobile computing. For that reason, how to understand and describe the concurrent mobile computing and how to develop their strictly-built mathematical models so that a solid theoretical foundation could be provided for further research, analysis, design, and validation of the actual concurrent system—all these problems become major challenges on computer science. Among those who respond to the challenges, the most successful one is Turing Award winner Professor Robin Miller and his collaborators, who promoted the Calculus of Communication System (CCS) to the formation of π-calculus in 1990’s [1 –5].

π-calculus, a concurrent theory with the research focus on inter-process mobile communication, supports dynamic system modeling and synchronous detection [6, 7]. Enjoying the strengths of simple mathematical structures and rich expressions, π-calculus is appropriate for describing the concurrent interactive system with the dynamic change of the topological structure [8 –10]. As the most basic concept in the π-calculus, names have been applied without distinction to label data values, data arguments, input parameters and channels which are used to deliver data [11 –18]. All these show great potentials of π-calculus in describing the present complex concurrent system, whose concurrency, mobility and distributive features are well demonstrated in the rules of π-calculus [19 –22].

Like any kind of description tools, π-calculus has been analyzed and compared in its descriptive ability with other tools by many experts and scholars right from the beginning. Robin Miller is no exception. In “Communicating and mobile systems: the π-calculus”, he discusses the perfect simulation of Lambda calculus with simple types, which has significant meanings, because it shows that the descriptive ability of π-calculus is at least as good as that of the simple-type Lambda calculus [1, 2].

The actual modeling of complex systems often requires sorting calculations. For example, in a system of a mobile phone conference with a fixed capacity, one needs to choose n appropriate users for the meeting according to the authority level from high to low. This involves the need to arrange the sequence for those who want to take part in the meeting and choose the first n users according to the authority level from high to low. However, π-calculus itself fails to offer the sorting operators to achieve the function. This paper hence aims to discuss the sorting problem of specified elements in well-ordered sets based on π-calculus with possible solutions.

2 Brief introduction of π-calculus

2.1 Interaction

In π-calculus, processes represent the units for concurrent operation entities, and each process has a number of channels for communication with other processes. Since both data and the channels used for delivering data are unanimously defined by names without any differentiation, processes and names are the two basic entities in π-calculus. So the interaction of π-calculus actually means data for two processes or two systems are communicated by usingchannels.

π-Calculus can be classified into monadic π-calculus and polyadic π-calculus. The former allows the number for an input or an output to be just one, while the latter allows the number for it to be either zero or multiple. Up to now, in comparison with the original definition of π-calculus, though there are many extensions, such as high order π-calculus and asynchronous π-calculus, the essence of π-calculus hasn’t gone through substantial changes.

The simple version of π-calculus interaction is illustrated in Fig. 1.

Fig.1

The simple version of π-calculus interaction.

In Fig. 1, the process P goes through the port b down the channel to send a message to the process Q, which receives it through the channel.

The concurrent version of π-calculus interaction is illustrated in Fig. 2.

Fig.2

The concurrent version of π-calculus interaction.

In Fig. 2, the process Q goes through the port a to send the message m to P1, which receives it through the same port from the same process Q. The process Q sends the message sequence $\vec{t}$ to the process P1 and the process P2 through the port b, so that both processes can receive the message sequence $\vec{t}$ from the process Q through the port b. The process Pn sends an empty message to the process Q through the port c. The punctuation ellipsis “ ... ... ” means the omitted processes or channels.

2.2 π-calculus syntax

In π-calculus, sending or receiving a message (or a name) or making a silent transition could be represented by action prefixes. Its syntax and corresponding meanings are:

π:: = m(n) receive the limited name n from the channel m.

m( $\vec{n}$ ) receive the limited name sequence $\vec{n}$ from the channel m (Notes: the number of the receiver and the sender must be the same).

$\bar{m} < n >$ send the free name n from the channel m.

$\bar{m} < \vec{n} >$ send the free name sequence $\vec{n}$ from the channel m (Notes: the number of the sender and the receiver must be the same).

τ is the internal action within the process, invisible from the outside.

The process P in π-calculus can be syntactically defined as: $P : : = \sum_{i \in I} π_{i} . P_{i} | P_{1} | P_{2} | new n P |! P$

∑_i∈Iπ_i . P_i is termed as a sum of the processes, in which I is the finite subscript set.

In the sum of the processes, π is guarded by π_i. That is, π has to start its action right after the action represented by π_i is finished.

The p1|p2 means the concurrent operation of the process P₁ and the process P₂.

The new n P means that the name n included in the process P is highly restricted or limited. Different from any other name outside P, this new n is quite unique even if it is still called n. For example, $P = new a (a . Q + b . R) | \bar{a} . 0) | (\bar{b} . S + \bar{a} . T)$ could lead to the two following deductions. $\begin{matrix} P \to new a (Q) | (\bar{b} . S + \bar{a} . T) \\ P \to new a (R) | \bar{a} . 0 | (S) \end{matrix}$

But the following deduction is wrong. $P \to n e w a (Q) | \bar{a} .0) | (T)$

!P means the concurrent operation of any multiple duplicates of P.

Similar to the sum of processes, $\prod_{i \in I} P_{i}$ could be used to mean the concurrent execution of multiple processes in order to achieve the conciseness of expressions, so the syntactic expression could be presented as: $P : : = \sum_{i \in I} π_{i} . P_{i} | \prod_{i \in I} P_{i} | new n P |! P$

3 π-calculus based realization of sorting elements based on a specified number in well-ordered sets

The sorting premise is that the elements that need sorting have to be in a partial order relation themselves. That is, those elements must be a subset of some partially ordered set. The conventional method is to compare the sorting elements in pairs. Suppose all the elements form into a well-ordered set which is stored in an ascending order in a linked list, we can compare in turns any two elements with all the elements in the well-ordered set by taking advantage of its transitivity. The matching feedback on the comparison can be applied to judge which of the two elements comes first (the sequence of the two elements). The comparison is effective if it’s targeted at only two elements, but when it comes to sorting multiple elements, there are two disadvantages. On one hand, if all the elements are compared in pairs, the underlying operation will suffer redundancy and lead to lower efficiency. On the other hand, if all the elements are compared in this way, then the strength of concurrency in π-calculus fails to be fully used to improve the sorting efficiency.

Thus, under the condition of sufficient resources, if we want to improve efficiency by using the concurrent nature of π-calculus, the following method is possible. First, the concurrent approach is adopted so that elements could be located in the well-ordered process, while those elements are put in the display process. After all the elements are located, the next thing to do is to find concurrently the successor of each element. In the end, according to the successor situation of each element, the pointer of each element in the display process will be adjusted concurrently. In this way, a well-ordered element list is completed.

3.1 The two proposed algorithms

The well-ordered process is mainly used as a benchmark, just like the alphabetical order. Suppose three letters a, b and d, need sorting, their sequence is decided by putting them into the alphabet-like well-ordered process. In the sorting algorithm, the well-ordered process could be repeatedly used.

There are three steps in the whole sorting process, which involves two simple concurrent algorithms: the looking-for-seats-in-the-cinema one (the cinema algorithm in short) and the changing-keys-among-a-group one (the key change algorithm in short).

First, elements are located in the well-ordered process (by using the cinema algorithms).

Second, the corresponding successor of each element is searched for in the well-ordered process (by using the cinema algorithms).

Third, the sorting is done according to the successor elements obtained (by using the key change algorithms).

The two algorithms are explained in greater details in the following section.

3.1.1 The cinema algorithm

The cinema algorithms: As the algorithm for the concurrent locating of elements, it is based on a simple idea, just like a group of people into the cinema for movies. That is, when everybody gets in together, they look for their own seats without interference among one another. This kind of concurrent algorithm is much more efficient than the one-by-one sequential algorithms, in which the next one starts to look for the seat only after the first one finds his. In the cinema algorithms, every element can set off unanimously from the starting point to move concurrently forward for the position in the sorting algorithms, or they each could set off from specified positions to move concurrently forward for their successor elements in the sorting algorithm.

In the linked list of Fig. 3, each node means that it has used the reproduction operator, which also means it could be used repeatedly in a concurrent way. Every three overlapping rectangles mean they have used the nodes of reproduction operators and the nodes can also be used repeatedly. The pentagram means that each element could concurrently look for its own position based on the sequence of the linked list.

Fig.3

Search for successors from the same starting point.

In comparison with earlier functional modeling languages, such as lambda calculus, π-calculus can describe and express features which cannot be described and expressed before. In this case, what can’t be described by lambda calculus, but can be described by π-calculus is the concurrent matching of elements with the well-ordered process. When the element matching is successful, the element will find out its own position just like a viewer finding out his own seat in the cinema, the only difference being that the element has to write itself into the result display process.

After successfully positioning in the well-ordered process, the element starts to take the next action: looking for its own subsequent element. It will not stop searching one after another in the well-ordered process until it finds out its own subsequent element.

In this sorting algorithm, the elements could do the matching to determine its own position in the well-ordered process, but in no way to determine which one is its successor. So the matching continues till the end of the well-ordered process. During the process, if it’s successfully matched by finding out its own position, it continues to perform the follow-up action. In order to know which one is the right one to be the successor element, a cache is necessary in the design. Unlike nodes in the well-ordered process, the cache cannot be used repeatedly, but just once. The cache is a successor location process which is segmented according to the elements that need sorting. In this process, the search will start from the next element in the well-ordered process till the end of the segmentation so that the successor element could be positioned in the sorting set. After the segmentation, each element looks concurrently for its own successor in the successor location process without interfering each other. One thing to be mentioned is that this method still belongs to the cinema algorithm.

Figure 4 is an illustration of list segmentation, in which each row represents a stage and the arrow down indicates the change. The first step is to segment the successor location process. After the segmentation is completed, the next thing for elements that need sorting is to look for their successor elements concurrently. In the Figure, each element (represented by a pentagram) will go through each node once (represented by a rectangle). Not necessarily subject to interference, they look forward for their own successors concurrently. When they find it out at the break point, the search stops.

Fig.4

Search for successors from different starting points.

In the search for successors, synchronization is a must. That is, only after the segmentation of the successor location process can elements start their search for successors, or a chaos would arise, because, under the condition of unfinished segmentation, the initiation of one element to search for its successor may go through unlimited searches and matchings all the way down, which will definitely disturb the searches of other elements.

After the completion of the search for successors, the next thing to do is the adjustment of the pointers for the result display process, by using the key change algorithm.

3.1.2 The key change algorithm

The key change algorithm: Suppose there are a group of dwarves, each living in their own house with only one key. Then their friend, a man with a normal size, comes to visit them. The rule is that every dwarf must have the key for the next door so that their friend only needs to have the key to the first dwarf. In this way, when he finishes visiting the first dwarf, he could have the key to the house of the next dwarf. And if this man wants, he could visit the houses of all the dwarves in the sequence like dominoes as illustrated in Fig. 5.

Fig.5

Visit each according to the sequence.

So now the question is that how the dwarves could get the key for the next house since all of them stay at their own with their own keys.

Then, there are another group of elves outside, with one man fewer than the dwarves. Everyone has the information of who the successor is for a corresponding dwarf without knowing other dwarves’ information. The dwarves also know which one of the elves has the information of their own successors. So when a dwarf confidently gives his key to the right elf, the elf will give the key to the dwarf’s successor. To dwarves, there are two ways of delivering the key. One is that the give-and-take actions between dwarves and elves are independent from each other, while the other is for the dwarf to give the key first and receive another later.

Although both ways are acceptable, their operations are quite different. In the independent way, two ports with different names have to be set up, with one responsible for giving the key and the other for receiving the key of the successor. As for the give-first-and-take-later way, only a port with one name is necessary, because the dwarf has to give his own key first through the name of the port before he uses the same name to receive the key of the successor. In comparison, the second way is a little less efficient than the first one, but its design is much more concise than the first one. Therefore, this paper prefers the second way in the successor algorithm.

Figure 6 is a simple illustration of this. This example assumes that there are four dwarves represented by people in the first line by the number 1, 2, 3 and 4, their sequence being based on the sequence of the number without any information of who their own successor is. Then there are three elves with the coding rule of (b,a) to indicate that b is the successor of a. For instance, Elf (4,3) means that he knows Dwarf No. 3’s successor is Dwarf No. 4, while Dwarf No. 4 also knows that Elf (4,3) has the information of who his predecessor is. So Dwarf No. 4 gives his room key to Elf (4,3) who gives it to Dwarf No. 3. In this way, Dwarf No. 3 gets the key of his successor, Dwarf No. 4.

Fig.6

Find the successors.

If the resources are rich enough, under the concurrent condition, the whole process could be completed just within two steps: First, Dwarf No. 4 gives his own key to Elf (4,3). At the meantime, Dwarf No. 3 gives his own key to Elf (3,2) and Dwarf No. 2 gives his own key to Elf (2,1). Second, Elf (4,3) gives Dwarf No. 4’s key to Dwarf No. 3. At the meantime, Elf (3,2) gives Dwarf No. 3’s key to Dwarf No. 2 and Elf (2,1) gives Dwarf No. 2’s key to Dwarf No. 1. Thus, the sorting process is completed through just two steps.

3.2 The detailed process realization

In the beginning, five concurrent processes need to be implemented, including: the controller process, the element set process, the well-ordered process, the successor location process and the result display process. The details are as follows.

3.2.1 The controller process

As the name is, the controller process is meant to control the whole sorting process. The expression of the controller process is as follows:

$\begin{matrix} (\prod_{i = 0}^{m - 1} \bar{{switch}_{i}} . \bar{{loopback}_{i}} < l_{0} >) | (\prod_{m} count) \\ . (\prod_{j = 0}^{m - 1} a_{j} (φ_{j}) . \bar{{change}_{j}} . \bar{{loopback}_{j}} < φ_{j} >) \\ . (\prod_{m - 1} count) . (\sum_{z = 0}^{n - 1} a_{z} (head))) \\ . (\sum_{z = 0}^{n - 1} \bar{a_{z}} < end >) . count \end{matrix}$ (1)

First, the cinema method is adopted to concurrently initiate the match between the element process and the well-ordered process for locating elements. After each element has located successfully with a match, it sends back a “count” message to the controller process. When the controller process receives m “count” messages (for example, 5 or 6 “count” messages), it means that all the elements are successfully located, while the successor location process is also successfully segmented. That is, a group of elves who deliver the key outside come to appear.

The well-ordered process will also send through the channel a_j a message of specified location φ_j to the controller process, telling the latter that the matching of the jth element with the successor location process must start from φ_j. In this way, “the group of elves delivering keys” will come into full formation. But it’s important to notice that forming “the group of elves” needs no synchronized operation. One doesn’t have to wait for the formation of all of them to start the procedure of “delivering the key”. Still, the controller process must also provide effective control and synchronized guidance over the procedure of “delivering the key”.

3.2.2 The element set process

First, suppose the elements that need sorting consist of a collection of A, a_v ∈ A and v ∈ N (N means the set of natural numbers), the expression of the element set process is as follows:

$\begin{matrix} \prod_{k = 0}^{m - 1} (! ({switch}_{k} + {change}_{k}) . {loopback}_{k} ({link}_{k}) . \\ \bar{{link}_{k}} < d_{k} {switch}_{k} {change}_{k} {ms}_{k} > . \\ (d_{k} (f_{k} t_{k}) . \bar{f_{k}} < a_{v} > . \bar{{loopback}_{k}} < t_{k} >)) \end{matrix}$ (2)

The element set process is concurrently made up of element sub-processes formed by m elements that need sorting. Mainly used in the concurrent storage of elements, the element set process focuses on sorting the content of elements, that is, a_v ∈ A. by matching respectively with the well-ordered process and the successor location process.

3.2.3 The well-ordered process

As the benchmark of element sorting, the well-ordered process serves as the standard, on the basis of which elements are identified with their relative position to judge their sequence. The expression of the well-ordered process is as follows:

$\begin{matrix} \prod_{y = 0}^{n - 1} (! l_{y} (c sw ch mr) \\ . \bar{c} < mr l_{y + 1} > | mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \bar{a_{y}} \\ < ξ_{2 y + 2} > . \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (3)

It is assumed without loss of generality that the element sequence in the well-ordered set is its subscript sequence. When the element has a successful match with the node of well-ordered process, the success will first lead to the segmentation towards the successor location process through ${\bar{ξ}}_{2 y + 1} < nil >$ . After the completion of the segmentation, a heartbeat count will be sent forward towards the controller process. Then by taking a_i as the channel, the well-ordered process sends to the controller process the node position information in the successor location process.

3.2.4 The successor location process

The successor location process is mainly used to find the corresponding successor of a specified element and send the information of the successor to the specified position of the result display process. The expression of the successor location process is as follows:

$\begin{matrix} \prod_{x = 0}^{n - 1} (ξ_{2 x} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 1} > \\ | mr (h_{2 x}) . \bar{ch} . a_{x} (θ) . \bar{h_{2 x}} < θ > | \\ ξ_{2 x + 1} (c sw ch mr) . \bar{c} \\ < mr ξ_{2 x + 2} > | mr (h_{2 x + 1}) . \bar{ch}) \end{matrix}$ (4)

In the successor location process, the nodes in odd numbers are empty nodes with no elements, performing two functions: one for connecting the next node and the other for being segmented. Similar to the well-ordered process, the successor location process also has to constantly driving the element set process (which includes the sorting elements) to do matching with it. But different from the well-ordered process, the successor location process is designed with an empty node after every element-contained node (the nodes in odd numbers must be empty as mentioned before). Besides, there is no reproduction operator in the successor location process, so the successor location process can only be used once.

3.2.5 The result display process

The result display process is used to store the elements that are already selected and sorted out in the well-ordered process, for the convenience of future reading according to the sequence used. The expression of the result display process as follows:

$\begin{matrix} \prod_{e = 0}^{n - 1} ({elem}_{e} (φ_{e}) . (\bar{φ_{e}} (ψ_{e}) . \\ \bar{count} . φ_{e} (δ_{e}) . ψ_{e} (c_{e}) . \bar{c_{e}} (m_{e} δ_{e}) | \bar{m_{e}} (φ_{e}))) \end{matrix}$ (5)

3.3 The concurrent mobile system

The sorting requires a concurrent mobile system composed of all the processes concurrently.

Controller | ElementarySets | WellOrder | SuccessorLocation | Result

3.3.1 The first proposed step

First the controller process concurrently sends messages through “switch” to the corresponding element set process. If a message is sent only through switch_g, then the controller process becomes:

$\begin{matrix} \bar{{loopback}_{g}} < l_{0} > | \prod_{i = 0, i \neq g}^{m - 1} (\bar{{switch}_{i}} . \bar{{loopback}_{i}} < l_{0} >) | \\ (\prod_{m} count) . (\prod_{j = 0}^{m - 1} a_{j} (φ_{j}) . \bar{{change}_{j}} . \bar{{loopback}_{j}} < φ_{j} >) . \\ (\prod_{m - 1} count) . (\sum_{z = 0}^{n - 1} a_{z} (head)) . (\sum_{z = 0}^{n - 1} \bar{a_{z}} < end >) . count \end{matrix}$ (6)

Since the sending action is concurrent, it has no influence on other actions. Suppose the switch messages with the subscripts g₁, g₂ … g_s have already concurrently sent out (and g₁, g₂ … g_s form a collection of G), suppose the loopback with the subscripts h₁, h₂ … h_u also concurrently send out the l₀ message (and h₁, h₂ … h_u form a collection of H having no intersection with G because the switch message sends first before loopback does), then the controller process becomes:

$\begin{matrix} \prod_{w \in G} \bar{{loopback}_{w}} < l_{0} > | \prod_{d = 0, d \notin G, d \notin H}^{m - 1} \bar{{switch}_{d}} . \bar{{loopback}_{d}} < l_{0} > | \\ (\prod_{m} count) . (\prod_{j = 0}^{m - 1} a_{j} (φ_{j}) . \bar{{change}_{j}} . \bar{{loopback}_{j}} < φ_{j} >) . \\ (\prod_{m - 1} count) . (\sum_{z = 0}^{n - 1} a_{z} (head)) . (\sum_{z = 0}^{n - 1} \bar{a_{z}} < end >) . count \end{matrix}$ (7)

When all the messages sent by switch and loopback have finished, the controller process becomes:

$\begin{matrix} (\prod_{m} count) . (\prod_{j = 0}^{m - 1} a_{j} (φ_{j}) . \bar{{change}_{j}} . \bar{{loopback}_{j}} < φ_{j} >) . \\ (\prod_{m - 1} count) . (\sum_{z = 0}^{n - 1} a_{z} (head)) . (\sum_{z = 0}^{n - 1} \bar{a_{z}} < end >) . count \end{matrix}$ (8)

As the concurrency is not interfered, the focus now is the analysis of the gth element sub-process in the element set process. When it receives the switch message sent from the controller process (following expression of 6), suppose the sub-process where the gth element is in the element set process has the element content a_s, the sub-process becomes:

$\begin{matrix} ({loopback}_{g} ({link}_{g}) . \bar{{link}_{g}} < d_{g} {switch}_{g} {change}_{g} {ms}_{g} > . \\ (d_{g} (f_{g} t_{g}) . \bar{f_{g}} < a_{s} > . \bar{{loopback}_{g}} < t_{g} >)) | \\ ! (({switch}_{g} + {change}_{g}) . {loopback}_{g} ({link}_{g}) . \\ \bar{{link}_{g}} < d_{g} {switch}_{g} {change}_{g} {ms}_{g} > . \\ (d_{g} (f_{g} t_{g}) . \bar{f_{g}} < a_{s} > . \bar{{loopback}_{g}} < t_{g} >)) \\ a_{s} \in A, s \in N N is a natural number . \end{matrix}$ (9)

In the expression (9), when the gth element in the element set process continues to receive $\bar{{loopback}_{g}} < l_{0} >$ from the controller process in (6), then the element set process becomes:

$\begin{matrix} \bar{l_{0}} < d_{g} {switch}_{g} {change}_{g} {ms}_{g} > . \\ (d_{g} (f_{g} t_{g}) . \bar{f_{g}} < a_{s} > . \bar{{loopback}_{g}} < t_{g} >) | \\ (! ({switch}_{g} + {change}_{g}) . {loopback}_{g} ({link}_{g}) . \\ \bar{{link}_{g}} < d_{g} {switch}_{g} {change}_{g} {ms}_{g} > . \\ (d_{g} (f_{g} t_{g}) . \bar{f_{g}} < a_{s} > . \bar{{loopback}_{g}} < t_{g} >)) \end{matrix}$ (10)

Of course, the action of l₀ sent by “loopback” in the controller process is concurrent. That is, the actions of l₀ received by multiple element sub-processes in the element set process are also concurrent. At this moment, the cinema algorithm has started to be used, with several elements beginning to look for their own positions in the well-ordered process starting from the initial pointer l₀.

3.3.2 The second proposed step

Following the expression (10), the gth element sub-process goes through $\bar{l_{0}} < d_{g} {switch}_{g} {change}_{g} {ms}_{g} >$ to send the pointer message to the well-ordered process. Then the gth element sub-process becomes:

$\begin{matrix} (d_{g} (f_{g} t_{g}) . \bar{f_{g}} < a_{s} > . \bar{{loopback}_{g}} < t_{g} >) | \\ (! ({switch}_{g} + {change}_{g}) . {loopback}_{g} ({link}_{g}) . \\ \bar{{link}_{g}} < d_{g} {switch}_{g} {change}_{g} {ms}_{g} > . \\ (d_{g} (f_{g} t_{g}) . \bar{f_{g}} < a_{s} > . \bar{{loopback}_{g}} < t_{g} >)) \end{matrix}$ (11)

The corresponding well-ordered process in expression of (8) becomes:

$\begin{matrix} \bar{d_{g}} < {ms}_{g} l_{1} > | {ms}_{g} (h_{0}) . \bar{{switch}_{g}} . \\ (a_{0} | \bar{h_{0}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \bar{{elem}_{0}} < a_{0} > | \\ \prod_{y = 0}^{n - 1} (! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > |! mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \bar{a_{y}} < ξ_{2 y} > . \bar{{elem}_{y}} < a_{y} >) \end{matrix}$ (12)

The expression is the action result targeted at the gth element sub-process in the element set process. Actually, due to concurrency, suppose several elements concurrently send the message l₀ to the well-ordered process, suppose these several elements are numbered consecutively to form a collection of V, then the well-ordered process becomes:

$\begin{matrix} \prod_{g^{'} \in V} (\bar{d_{g^{'}}} < {ms}_{g^{'}} l_{1} > | {ms}_{g^{'}} (h_{0}) . \bar{{switch}_{g^{'}}} . \\ (a_{0} | \bar{h_{0}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \bar{{elem}_{0}} < a_{0} >)) | \\ \prod_{y = 0}^{n - 1} ((! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > |! mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \bar{a_{y}} < ξ_{2 y} > . \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (13)

Under the condition of no interference to concurrency, the single action could be well analyzed (in the expression of 12). Suppose the well-ordered process sends a message through $\bar{d_{g}} < {ms}_{g} l_{1} >$ to the corresponding gth element of the element set process (in the expression of 11), the gth element sub-process becomes:

$\begin{matrix} (\bar{{ms}_{g}} < a_{s} > . \bar{{loopback}_{g}} < l_{1} >) | \\ ! (({switch}_{g} + {change}_{g}) . {loopback}_{g} ({link}_{g}) . \\ \bar{{link}_{g}} < d_{g} {switch}_{g} {change}_{g} {ms}_{g} > . \\ (d_{g} (f_{g} t_{g}) . \bar{f_{g}} < a_{s} > . \bar{{loopback}_{g}} < t_{g} >)) \end{matrix}$ (14)

Following the expression of (12), if the well-ordered process sends out $\bar{d_{g}} < m_{1} l_{1} >$ , it becomes:

$\begin{matrix} {ms}_{g} (h_{0}) . \bar{{switch}_{g}} . \\ (a_{0} | \bar{h_{0}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \bar{{elem}_{0}} < a_{0} > | \\ \prod_{y = 0}^{n - 1} (! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > |! mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \\ \bar{a_{y}} < ξ_{2 y} > . \bar{{elem}_{y}} < a_{y} >) \end{matrix}$ (15)

Under the concurrency or the situation of the expression of 13), the well-ordered process that sends out $\bar{d_{g}} < m_{1} l_{1} >$ becomes:

$\begin{matrix} {ms}_{g} (h_{0}) . \bar{{switch}_{g}} . \\ (a_{0} | \bar{h_{0}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \bar{{elem}_{0}} < a_{0} >) | \\ \prod_{g^{'} \in V, g^{'} \neq g} (\bar{d_{g^{'}}} < {ms}_{g^{'}} l_{1} > | {ms}_{g^{'}} (h_{0}) . \bar{{switch}_{g^{'}}} . \\ (a_{0} | \bar{h_{0}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \bar{{elem}_{0}} < a_{0} >)) | \\ \prod_{y = 0}^{n - 1} ((! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > |! mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \bar{a_{y}} < ξ_{2 y} > . \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (16)

If d_g′ messages all finish sending out, the well-ordered process becomes:

$\begin{matrix} \prod_{g^{'} \in V} ({ms}_{g^{'}} (h_{0}) . \bar{{switch}_{g^{'}}} . \\ (a_{0} | \bar{h_{0}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \bar{{elem}_{0}} < a_{0} >)) | \\ \prod_{y = 0}^{n - 1} ((! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > |! mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \bar{a_{y}} < ξ_{2 y} > . \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (17)

Following the expression of (14), the gth element sub-process can send the element message a_s through ms_g to the well-ordered process and the gth element sub-process becomes:

$\begin{matrix} \bar{{loopback}_{g}} < l_{1} > |! (({switch}_{g} + {change}_{g}) . \\ {loopback}_{g} ({link}_{g}) . \\ \bar{{link}_{g}} < d_{g} {switch}_{g} {change}_{g} {ms}_{g} > . \\ (d_{g} (f_{g} t_{g}) . \bar{f_{g}} < a_{s} > . \bar{{loopback}_{g}} < t_{g} >)) \end{matrix}$ (18)

Under the concurrent situation, the well-ordered process changes on the base of the expression (16). So when the gth element sub-process sends the element message a_s through ms_g to the well-ordered process, the well-ordered process becomes:

$\begin{matrix} \bar{{switch}_{g}} . (a_{0} | \bar{h_{0}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \bar{{elem}_{0}} < a_{0} >) | \\ \prod_{g^{'} \in V, g^{'} \neq g} (\bar{d_{g^{'}}} < {ms}_{g^{'}} l_{1} > | {ms}_{g^{'}} (h_{0}) . \bar{{switch}_{g^{'}}} . \\ (a_{0} | \bar{h_{0}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \bar{{elem}_{0}} < a_{0} >)) | \\ \prod_{y = 0}^{n - 1} ((! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > |! mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \bar{a_{y}} < ξ_{2 y} > . \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (19)

If the well-ordered process changes on the base of the expression (2.12), the well-ordered process becomes:

$\begin{matrix} \bar{{switch}_{g}} . (a_{0} | \bar{a_{s}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \\ \bar{{elem}_{0}} < a_{0} >) | \prod_{g^{'} \in V, g^{'} \neq g} ({ms}_{g^{'}} (h_{0}) . \bar{{switch}_{g^{'}}} . \\ (a_{0} | \bar{h_{0}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \bar{{elem}_{0}} \\ < a_{0} >)) | \prod_{y = 0}^{n - 1} ((! l_{y} (c sw ch mr) . \\ \bar{c} < mr l_{y + 1} > |! mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \bar{a_{y}} < ξ_{2 y} > . \\ \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (20)

Following the expression of (19), if $\bar{{switch}_{g}}$ corresponding to the well-ordered process sends out, then the switch_g + change_g of the gth element sub-process (in the expression of 18) releases the guard, the gth element sub-process becomes:

$\begin{matrix} \bar{{loopback}_{g}} < l_{1} > | {loopback}_{g} ({link}_{g}) . \\ \bar{{link}_{g}} < d_{g} {switch}_{g} {change}_{g} {ms}_{g} > . \\ (d_{g} (f_{g} t_{g}) . \bar{f_{g}} < a_{s} > . \bar{{loopback}_{g}} < t_{g} >) | \\ ! (({switch}_{g} + {change}_{g}) . {loopback}_{g} ({link}_{g}) . \\ \bar{{link}_{g}} < d_{g} {switch}_{g} {change}_{g} {ms}_{g} > . \\ (d_{g} (f_{g} t_{g}) . \bar{f_{g}} < a_{s} > . \bar{{loopback}_{g}} < t_{g} >)) \end{matrix}$ (21)

The well-ordered process based on the expression (19) becomes:

$\begin{matrix} (a_{0} | \bar{h_{0}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \bar{{elem}_{0}} < a_{0} >) | \\ \prod_{g^{'} \in V, g^{'} \neq g} (\bar{d_{g^{'}}} < {ms}_{g^{'}} l_{1} > | {ms}_{g^{'}} (h_{0}) . \bar{{switch}_{g^{'}}} . \\ (a_{0} | \bar{h_{0}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \bar{{elem}_{0}} < a_{0} >)) | \\ \prod_{y = 0}^{n - 1} ((! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > |! mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \bar{a_{y}} < ξ_{2 y} > . \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (22)

The well-ordered process based on the expression (20) becomes:

$\begin{matrix} a_{0} | \bar{a_{s}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \bar{{elem}_{0}} < a_{0} > | \\ \prod_{g^{'} \in V, g^{'} \neq g} ({ms}_{g^{'}} (h_{0}) . \bar{{switch}_{g^{'}}} . \\ (a_{0} | \bar{h_{0}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{0} > . \bar{{elem}_{0}} < a_{0} >)) | \\ \prod_{y = 0}^{n - 1} ((! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > |! mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \bar{a_{y}} < ξ_{2 y} > . \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (23)

In the gth element sub-process based on the expression (21), its internal part makes a delivery of the message l₁ through loopback. In this way, as far as the gth element sub-process is concerned, the pointer moves from l₀ to l₁ and the gth element sub-process becomes:

$\begin{matrix} \bar{l_{1}} < d_{g} {switch}_{g} {change}_{g} {ms}_{g} > . \\ (d_{g} (f_{g} t_{g}) . \bar{f_{g}} < a_{s} > . \bar{{loopback}_{g}} < t_{g} >) | \\ ! (({switch}_{g} + {change}_{g}) . {loopback}_{g} ({link}_{g}) . \\ \bar{{link}_{g}} < d_{g} {switch}_{g} {change}_{g} {ms}_{g} > . \\ (d_{g} (f_{g} t_{g}) . \bar{f_{g}} < a_{s} > . \bar{{loopback}_{g}} < t_{g} >)) \end{matrix}$ (24)

In this way, the node pointer of the gth element sub-process moves from l₀ to l₁. When the gth element sub-process constantly matches with the well-ordered process and constantly sends the corresponding element information to every node of the well-ordered process, such interaction will lead the well-ordered process to change partially into:

The interaction of every element set process with the well-ordered process will lead to concurrent overlaying. That is, every element sub-process, just like the gth element sub-process, will end up with matching to its own position in the well-ordered process. Besides, all the sub-processes are concurrent and independent from each other. For example, the gth element sub-process can do matching concurrently (without loss of generality), so when a_s in the gth element sub-process has already matched but hasn’t yet made self-reaction within the well-ordered process, while at this moment, a_w of the uth element sub-process has already come to the position, then the well-ordered process becomes:

$\begin{matrix} (a_{0} | \bar{a_{s}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{2} > . \bar{{elem}_{0}} < a_{0} >) | \\ . . . . . . \\ (a_{s} | \bar{a_{s}} . {\bar{ξ}}_{2 s + 1} < nil > . \bar{count} . \bar{a_{s}} < ξ_{2 s + 2} > . \bar{{elem}_{s}} < a_{s} >) | \\ . . . . . . \\ (a_{0} | \bar{a_{w}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{2} > . \bar{{elem}_{0}} < a_{0} >) | \\ . . . . . . \\ (a_{w} | \bar{a_{w}} . {\bar{ξ}}_{2 w + 1} < nil > . \bar{count} . \bar{a_{w}} < ξ_{2 w + 2} > . \bar{{elem}_{w}} < a_{w} >) | \\ . . . . . . \\ \prod_{y = 0}^{n - 1} ((! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > | \\ ! mr (h_{y}) . \bar{sw} . (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \\ \bar{a_{y}} < ξ_{2 y + 2} > . \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (26)

When a_w is in position, and a_s has already made the self reaction in the, then the well-ordered process becomes:

$\begin{matrix} (a_{0} | \bar{a_{s}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{2} > . \bar{{elem}_{0}} < a_{0} >) | \\ . . . . . . \\ ({\bar{ξ}}_{2 s + 1} < nil > . \bar{count} . \bar{a_{s}} < ξ_{2 s + 2} > . \bar{{elem}_{s}} < a_{s} >) | \\ . . . . . . \\ (a_{0} | \bar{a_{w}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{2} > . \bar{{elem}_{0}} < a_{0} >) | \\ . . . . . . \\ (a_{w} | \bar{a_{w}} . {\bar{ξ}}_{2 w + 1} < nil > . \bar{count} . \bar{a_{w}} < ξ_{2 w + 2} > . \\ \bar{{elem}_{w}} < a_{w} >) | \\ . . . . . . \\ \prod_{y = 0}^{n - 1} ((! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > | \\ ! mr (h_{y}) . \bar{sw} . (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \\ \bar{a_{y}} < ξ_{2 y + 2} > . \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (27)

In the well-ordered process, when the ith element successfully does the matching, it sends the message through ${\bar{ξ}}_{2 i + 1} (nil)$ to the successor location process in order to make the segmentation at 2i+1 in the successor location process. In this way, the successor location process can be segmented from a complete link into several disconnected smaller links, which relatively limit the location comparison between elements within some smaller link, instead of affecting the location comparison between other elements, because there is no reproduction operator in the successor location process. Therefore, when all the comparisons are done for just once with every element limited in its own space, the segmentation can stop the current element matching from going further.

If the segmentation is done towards the successor location process through ${\bar{ξ}}_{2 p + 1} (nil, nil, nil, nil)$ , (following the expression of 4) the successor location process becomes:

$\begin{matrix} \prod_{x = 0}^{p - 1} ((ξ_{2 x} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 1} > | mr (h_{2 x}) . \\ \bar{ch} . a_{x} (θ) . \bar{h_{2 x}} < θ >) | \\ (ξ_{2 x + 1} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 2} > | mr (h_{2 x + 1}) . ch)) | \\ (ξ_{2 p} (c sw ch mr) . \bar{c} < mr ξ_{2 p + 1} > | mr (h_{2 p}) . \\ \bar{ch} . a_{p} (θ) . \bar{h_{2 p}} < θ >) | \\ \bar{nil} < nil ξ_{2 p + 2} > | nil (h_{2 p + 1}) . nil) | \\ \prod_{x = p + 1}^{n - 1} ((ξ_{2 x} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 1} > | mr (h_{2 x}) . \\ \bar{ch} . a_{x} (θ) . \bar{h_{2 x}} < θ >) | \\ (ξ_{2 x + 1} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 2} > | mr (h_{2 x + 1}) . \bar{ch})) \\ (1 < p < n - 2) \end{matrix}$ (28)

The difference between the expression (28) and (9) lies in the empty node of the third line in (28). It is equivalent to being cut off, the action of which leads to the disconnection of the linked list of the successor location process from here. That is, suppose an element set process should want to do the matching before the position of 2p, it would be impossible for the matching to jump from 2p-1 to 2p+1, since the empty node at 2p that serves as the connector has already been cut off.

It is assumed that m elements need the segmentation for m times at the successor location process. Suppose the segmentation starts from s₁ to s_m without loss of generality, suppose it goes like this 1 < s₁ < s₂ < … < s_m, then the result of the segmentation of the successor location process becomes:

$\begin{matrix} \prod_{x = 0}^{s_{1} - 1} ((ξ_{2 x} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 1} > | mr (h_{2 x}) . \\ \bar{ch} . a_{x} (θ) . \bar{h_{2 x}} < θ >) | \\ (ξ_{2 x + 1} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 2} > | mr (h_{2 x + 1}) . \bar{ch})) | \\ (ξ_{2 s_{1}} (c sw ch mr) . \bar{c} < mr ξ_{2 s_{1} + 1} > | mr (h_{2 s_{1}}) . \bar{ch} . \\ a_{s_{1}} (θ) . \bar{h_{2 s_{1}}} < θ >) | \\ \bar{nil} < nil ξ_{2 s_{1} + 2} > | nil (h_{2 s_{1} + 1}) . nil) | \\ \prod_{x = s_{1} + 1}^{s_{2} - 1} ((ξ_{2 x} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 1} > | mr (h_{2 x}) . \\ \bar{ch} . a_{x} (θ) . \bar{h_{2 x}} < θ >) | \\ (ξ_{2 x + 1} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 2} > | mr (h_{2 x + 1}) . \bar{ch})) | \\ . . . \\ \prod_{x = s_{m - 1} + 1}^{s_{m} - 1} ((ξ_{2 x} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 1} > | mr (h_{2 x}) . \\ \bar{ch} . a_{x} (θ) . \bar{h_{2 x}} < θ >) | \\ (ξ_{2 x + 1} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 2} > | mr (h_{2 x + 1}) . \bar{ch})) | \\ (ξ_{2 s_{m}} (c sw ch mr) . \bar{c} < mr ξ_{2 s_{m} + 1} > | mr (h_{2 s_{m}}) . \\ ch . a_{s_{m}} (θ) . \bar{h_{2 s_{m}}} < θ > | \\ \bar{nil} < nil ξ_{2 s_{m} + 2} > | nil (h_{2 s_{m} + 1}) . nil) | \\ \prod_{x = s_{m} + 1}^{n - 1} ((ξ_{2 x} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 1} > | mr (h_{2 x}) . \\ \bar{ch} . a_{x} (θ) . \bar{h_{2 x}} < θ > | \\ (ξ_{2 x + 1} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 2} > | mr (h_{2 x + 1}) . \bar{ch})) \end{matrix}$ (29)

Following the expression (27), after the well-ordered process sends out ${\bar{ξ}}_{2 s + 1} < nil >$ , it becomes:

$\begin{matrix} (a_{0} | \bar{a_{s}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{2} > . \bar{{elem}_{0}} < a_{0} >) | \\ . . . . . . \\ (\bar{count} . \bar{a_{s}} < ξ_{2 s + 2} > . \bar{{elem}_{s}} < a_{s} >) | \\ . . . . . . \\ (a_{0} | \bar{a_{w}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{2} > . \bar{{elem}_{0}} < a_{0} >) | \\ . . . . . . \\ (a_{w} | \bar{a_{w}} . {\bar{ξ}}_{2 w + 1} < nil > . \bar{count} . \bar{a_{w}} < ξ_{2 w + 2} > . \\ \bar{{elem}_{w}} < a_{w} >) | \\ . . . . . . \\ \prod_{y = 0}^{n - 1} ((! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > |! mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \\ \bar{a_{y}} < ξ_{2 y + 2} > . \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (30)

3.3.3 The third proposed step

After the successor location process finishes its segmentation after the reaction between all the compared elements and the well-ordered process, the complete link of the successor location process will be cut into several smaller links. That is, the group of elves who are going to deliver the keys in the key change algorithm comes into its embryonic form. Only when the successor location process is segmented into several parts can the element location and the resorting in the later result display process avoid interference with each other, which is crucial to the concurrent design and analysis, because it could circumvent the unstable actions of possible explosive combinations.

But how could one guarantee that the completion of the reactions of the element set processes must be followed by their reactions with the segmented successor location processes and further followed by re-locating in the result display process? The answer is the heartbeat count information $\bar{count}$ .

After the segmented message of the well-ordered process ${\bar{ξ}}_{2 g + 1} < nil >$ has been sent out, the well-ordered process sends out the information of heartbeat counts $\bar{count}$ to the controller process. When the controller process receives m count messages, it means that all the nodes that need segmentation have finished the action. The completion of the segmentation can stop the matching of the unrelated element set processes from sabotaging every matching element set process by confining it within its own area without transgressing. Following the expression (8), the controller process at this moment becomes:

$\begin{matrix} (\prod_{j = 0}^{m - 1} a_{j} (φ_{j}) . \bar{{change}_{j}} . \bar{{loopback}_{j}} < φ_{j} >) . \\ (\prod_{m - 1} count) . (\sum_{z = 0}^{n - 1} a_{z} (head)) . \\ (\sum_{z = 0}^{n - 1} \bar{a_{z}} < end >) . count \end{matrix}$ (31)

At this moment, the controller process can concurrently initiate the matching of the element set process and the successor location process.

As far as the expression (30) is concerned, the well-ordered process has become:

$\begin{matrix} (a_{0} | \bar{a_{s}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{2} > . \bar{{elem}_{0}} < a_{0} >) | \\ . . . . . . \\ (\bar{a_{s}} < ξ_{2 s + 2} > . \bar{{elem}_{s}} < a_{s} >) | \\ . . . . . . \\ (a_{0} | \bar{a_{w}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{2} > . \bar{{elem}_{0}} < a_{0} >) | \\ . . . . . . \\ (a_{w} | \bar{a_{w}} . {\bar{ξ}}_{2 w + 1} < nil > . \bar{count} . \\ \bar{a_{w}} < ξ_{2 w + 2} > . \bar{{elem}_{w}} < a_{w} >) | \\ . . . . . . \\ \prod_{y = 0}^{n - 1} ((! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > |! mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \bar{a_{y}} < ξ_{2 y + 2} > . \\ \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (32)

Then the well-ordered process sends to the controller process through the channel a the successor location information which has been segmented by nodes in the successor location process. The information contains the initial position of the comparison a. Suppose it uses the channel a_s to send the information, following the expression (32), the well-ordered process becomes:

$\begin{matrix} (a_{0} | \bar{a_{s}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{2} > . \bar{{elem}_{0}} < a_{0} >) | \\ . . . . . . \\ (\bar{{elem}_{s}} < a_{s} >) | \\ . . . . . . \\ (a_{0} | \bar{a_{w}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{2} > . \bar{{elem}_{0}} < a_{0} >) | \\ . . . . . . \\ (a_{w} | \bar{a_{w}} . {\bar{ξ}}_{2 w + 1} < nil > . \bar{count} . \bar{a_{w}} < ξ_{2 w + 2} > . \\ \bar{{elem}_{w}} < a_{w} >) | \\ . . . . . . \\ \prod_{y = 0}^{n - 1} ((! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > |! mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \bar{a_{y}} < ξ_{2 y + 2} > . \\ \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (33)

Following (31), suppose the controller process receives the message of ξ_2s+2 from the element set process through the channel a_s, then the controller process becomes:

$\begin{matrix} (\bar{{change}_{s}} . \bar{{loopback}_{s}} < ξ_{2 s + 2} >) | \\ (\prod_{j = 0, j \neq s}^{m - 1} a_{j} (φ_{j}) . \bar{{change}_{j}} . \bar{{loopback}_{j}} < φ_{j} >) . \\ (\prod_{m - 1} count) . (\sum_{z = 0}^{n - 1} a_{z} (head)) . \\ (\sum_{z = 0}^{n - 1} \bar{a_{z}} < end >) . count \end{matrix}$ (34)

ξ_2s+2 marks the gth element sub-process. At the initial comparing position in the successor location process, after $\bar{{change}_{g}}$ initiates the comparison, the controller process sends out through $\bar{{loopback}_{g}} < ξ_{2 g + 2} >$ the information of the initial position to the element set process. Then the gth element sub-process can go to the successor location process to look for the corresponding initial position for matching. With the operation similar to the previous matching between the element set process and the well-ordered process, the controller process also deals with the matching operation by initiating the message (change) first right before the initial position message (loopback).

Immediately after the well-ordered process sends out the location information related to the location process through the channel a, it can send a_g through elem to the result display process for the element construction in the result display process, which is the embryonic form of the sorting results. Following the expression (33), the well-ordered process, after sending out elem, becomes:

$\begin{matrix} (a_{0} | \bar{a_{s}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{2} > . \bar{{elem}_{0}} < a_{0} >) | \\ . . . . . . \\ () | \\ . . . . . . \\ (a_{0} | \bar{a_{w}} . {\bar{ξ}}_{1} < nil > . \bar{count} . \bar{a_{0}} < ξ_{2} > . \bar{{elem}_{0}} < a_{0} >) | \\ . . . . . . \\ (a_{w} | \bar{a_{w}} . {\bar{ξ}}_{2 w + 1} < nil > . \bar{count} . \bar{a_{w}} < ξ_{2 w + 2} > . \\ \bar{{elem}_{w}} < a_{w} >) | \\ . . . . . . \\ \prod_{y = 0}^{n - 1} ((! l_{y} (c sw ch mr) . \bar{c} < mr l_{y + 1} > |! mr (h_{y}) . \bar{sw} . \\ (a_{y} | \bar{h_{y}} . {\bar{ξ}}_{2 y + 1} < nil > . \bar{count} . \bar{a_{y}} < ξ_{2 y + 2} > . \\ \bar{{elem}_{y}} < a_{y} >)) \end{matrix}$ (35)

It is noticed that, in relation to the expression (32), the fifth line of the expression (35) has already been empty. Although the third line could surely be omitted in the expression, it’s better for the empty line to be written between the expressions for the convenience of comparison and observation. So the well-ordered process sends out messages through elem to the result display process. Without loss of generality, it is assumed that only the message a_s is sent out. After it being sent out, following the expression (5), the result display process becomes:

$\begin{matrix} ((\bar{a_{s}} < ψ_{s} > . \bar{count} . a_{s} (δ_{s})) . ψ_{s} (c_{s}) . \bar{c_{s}} < m_{s} δ_{s} > | \\ \bar{m_{s}} < a_{s} >) | \prod_{e = 0, e \neq s}^{n - 1} ({elem}_{e} (φ_{e}) . \\ (\bar{φ_{e}} < ψ_{e} > . \bar{count} . φ_{e} (δ_{e}) . ψ_{e} (c_{e}) . \\ \bar{c_{e}} < m_{e} δ_{e} > | \bar{m_{e}} < φ_{e} >) \end{matrix}$ (36)

After the result display process reacts with the element set process, the result display process becomes:

$\begin{matrix} \prod_{s = 0}^{n - 1} ((\bar{a_{s}} < ψ_{s} > . \bar{count} . a_{s} (δ_{s})) . ψ_{s} (c_{s}) . \\ \bar{c_{s}} < m_{s} δ_{s} > | \bar{m_{s}} < a_{s} >) \end{matrix}$ (37)

As the expressions are concurrent in the result display process, various element information can be sent from the well-ordered process concurrently without the interference among one another, thereby taking the first step towards the construction of the result display process (that is, filling elements into the result display process.

After the elements successfully enter the result display process, what is left is to determine the final direction of the pointer δ through its interaction with the successor location process.

The whole process is illustrated in Fig. 7:

Fig.7

Illustration of searching for successor.

Following the expression of (29), it is assumed that the element a_{s_m-1} starts to look for its own successor in the successor location process. At first, the well-ordered process sends to the controller process the information of the initial position for comparison (similar to the expression of 32). Then, the controller process sends to the element set process, which initiates the comparison from . The matching process is like the viewer’s looking for his successor in the cinema. Suppose his successor was somewhere on his left, and suppose he had an infinitely long left hand, he would search down his left side with his left hand. Every time he touched someone, he would have to judge whether the one he touches is his successor. He would keep touching till his hand touches one marked place, the segmented node where he has to stop searching further. The comparison between the element set process and the successor location process is quite similar to the one between the element set process and the well-ordered process. For example, an element set process containing a_{s
_m-1} is assumed to start the comparison at . Following the expression (29), after the segmentation, under the effect of the matching with the element set process that contains a_{s
_m-1}, the successor location processbecomes:

$\begin{matrix} \prod_{x = 0}^{s_{1} - 1} ((ξ_{2 x} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 1} > \\ | mr (h_{2 x}) . \bar{ch} . a_{x} (θ) . \bar{h_{2 x}} < θ >) | \\ (ξ_{2 x + 1} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 2} > | mr (h_{2 x + 1}) . \bar{ch})) | \\ (ξ_{2 s_{1}} (c sw ch mr) . \bar{c} < mr ξ_{2 s_{1} + 1} > | mr (h_{2 s_{1}}) . \\ \bar{ch} . a_{s_{1}} (θ) . \bar{h_{2 s_{1}}} < θ > | \\ \bar{nil} < nil ξ_{2 s_{1} + 2} > | nil (h_{2 s_{1} + 1}) . nil) | \\ \prod_{x = s_{1} + 1}^{s_{2} - 1} ((ξ_{2 x} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 1} > | mr (h_{2 x}) . \\ \bar{ch} . a_{x} (θ) . \bar{h_{2 x}} < θ > | \\ (ξ_{2 x + 1} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 2} > | mr (h_{2 x + 1}) . \bar{ch})) | \\ . . . \\ (\prod_{x = s_{m - 1} + 1}^{s_{m}} (a_{x} (θ) . \bar{a_{s_{m}}} < θ >) | \bar{nil} < nil ξ_{2 s_{m} + 2} > \\ | nil (h_{2 s_{m} + 1}) . nil) | \\ . . . \\ \prod_{x = s_{m} + 1}^{n - 1} ((ξ_{2 x} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 1} > \\ | mr (h_{2 x}) . \bar{ch} . a_{x} (θ) . \bar{h_{2 x}} < θ > | \\ (ξ_{2 x + 1} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 2} > \\ | mr (h_{2 x + 1}) . \bar{ch})) \end{matrix}$ (38)

If all the matchings are done, the successor location process becomes:

$\begin{matrix} \prod_{x = 0}^{s_{1} - 1} ((ξ_{2 x} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 1} > \\ | mr (h_{2 x}) . \bar{ch} . a_{x} (θ) . \bar{h_{2 x}} < θ >) | \\ (ξ_{2 x + 1} (c sw ch mr) . \bar{c} < mr ξ_{2 x + 2} > \\ | mr (h_{2 x + 1}) . \bar{ch})) | \\ (\prod_{x = s_{1} + 1}^{s_{2}} (a_{x} (θ) . \bar{a_{s_{1}}} < θ >) | \bar{nil} < nil ξ_{2 s_{2} + 2} > \\ | nil (h_{2 s_{2} + 1}) . nil) | \\ . . . \\ (\prod_{x = s_{k - 1} + 1}^{s_{k}} (a_{x} (θ) . \bar{a_{s_{k - 1}}} < θ >) | \bar{nil} < nil ξ_{2 s_{k - 1} + 2} > \\ | nil (h_{2 s_{k - 1} + 1}) . nil) | \\ . . . \\ (\prod_{x = s_{m} + 1}^{n} (a_{x} (θ) . \bar{a_{s_{m}}} < θ >) | \\ \bar{nil} < nil ξ_{2 s_{m} + 2} > | nil (h_{2 s_{m} + 1}) . nil \end{matrix}$ (39)

Actually, the matching between the element set process and the successor location process and the one between the result display process and the successor location process are carried outconcurrently.

In the expression of (36), $\bar{a_{i}} < ψ_{i + 1} >$ means sending to the successor location process the information ψ_i+1, which is the position of a_i in the result display process. a_i (δ_i+1) means receiving the successor of a_i from to the successor location process. This is one of the most important steps in key change algorithm: giving out the house key first.

After the controller process concurrently initiates the comparison between the element set process and the successor set process (following the expression 31), the successor location process also has a corresponding change (following the expression 29). Suppose a_k is located before a_s, then in the comparison there appears $a_{k} (θ) . \bar{a_{s}} < θ >$ .

Mean while, after the reaction with the element set process, the result display process becomes:

$\begin{matrix} ((\bar{a_{s_{1}}} < ψ_{s_{1}} > . \bar{count} . a_{s_{1}} (δ_{s_{1}})) . ψ_{s_{1}} (c_{s_{1}}) . \\ \bar{c_{s_{1}}} < m_{s_{1}} δ_{s_{1}} > | \bar{m_{s_{1}}} < a_{s_{1}} >) | \\ ((\bar{a_{s_{2}}} < ψ_{s_{2}} > . \bar{count} . a_{s_{2}} (δ_{s_{2}})) . ψ_{s_{2}} (c_{s_{2}}) . \\ \bar{c_{s_{2}}} < m_{s_{2}} δ_{s_{2}} > | \bar{m_{s_{2}}} < a_{s_{2}} >) | \\ . . . \\ ((\bar{a_{s_{m}}} < ψ_{s_{m}} > . \bar{count} . a_{s_{m}} (δ_{s_{m}})) . ψ_{s_{m}} (c_{s_{m}}) . \\ \bar{c_{s_{m}}} < m_{s_{m}} δ_{s_{m}} > | \bar{m_{s_{m}}} < a_{s_{m}} >) | \\ \prod_{e = 0, e \notin {s_{1} . . s_{m}}}^{n - 1} {elem}_{e} (φ_{e}) . \\ ((\bar{φ_{e}} < ψ_{e} > . \bar{count} . φ_{e} (δ_{e})) . ψ_{e} (c_{e}) . \\ \bar{c_{e}} < m_{e} δ_{e} > | \bar{m_{e}} < φ_{e} >) \end{matrix}$ (40)

Following (34), the controller process receives from the well-ordered process the information of the corresponding initial positions of all the elements that need sorting. After the controller process finishes initiating all the matchings between the element set process and the successor location process, it becomes as follows:

$\begin{matrix} (\prod_{m - 1} count) . (\sum_{z = 0}^{n - 1} a_{z} (head)) . \\ (\sum_{z = 0}^{n - 1} \bar{a_{z}} < end >) . count \end{matrix}$ (41)

The reactions between the result display process, the controller process and the successor location process finally lead the result display process to become

$\begin{matrix} (ψ_{s_{1}} (c_{s_{1}}) . \bar{c_{s_{1}}} < m_{s_{1}} ψ_{s_{2}} > | \bar{m_{s_{1}}} < a_{s_{1}} >) | \\ ψ_{s_{2}} (c_{s_{2}}) . \bar{c_{s_{2}}} < m_{s_{2}} ψ_{s_{3}} > | \bar{m_{s_{2}}} < a_{s_{2}} >) | \\ . . . \\ ψ_{s_{m - 1}} (c_{s_{m - 1}}) . \bar{c_{s_{m - 1}}} < m_{s_{m - 1}} ψ_{s_{m}} > \\ | \bar{m_{s_{m - 1}}} < a_{s_{m - 1}} >) | \\ (ψ_{s_{m}} (c_{s_{m}}) . \bar{c_{s_{m}}} < m_{s_{m}} end > | \bar{m_{s_{m}}} < a_{s_{m}} >) | \\ \prod_{e = 0, e \notin {s_{1} . . s_{m}}}^{n - 1} ({elem}_{e} (φ_{e}) . \\ ((\bar{φ_{e}} < ψ_{e} > . \bar{count} . φ_{e} (δ_{e})) . ψ_{e} (c_{e}) . \bar{c_{e}} < m_{e} δ_{e} > | \\ \bar{m_{e}} < φ_{e} >)) \end{matrix}$ (42)

In this way, the sorting is completed with the effective part of the sorting results as illustrated in Fig. 8:

Fig.8

Illustration of the result after the sorting is done.

Therefore, the result display process will show the sorting results of the elements that need sorting. (What has to be noticed is that ψ₃ has been sent to the controller process as the head, but its treatment is omitted in this paper for the convenience of discussion.) After the sorting is done, it’s handy to read the sorting elements according to the sequence. The reading manner is quite similar to that of matching between the element set process and the well-ordered process or between the element set process and successor location process, but the reading sequence on well-sorted elements will not be further discussed here because it’s not the focus of this paper.

4 Conclusion

The conventional sorting algorithm is based on the sequential description. However, under the situation of increasing resources, particularly when the units that need to be dealt with are increasing, the sorting of the elements based on the well-ordered set will suffer from the poverty of computing efficiency. In the paper, this problem is well solved by the concurrent mobile sorting based on π calculus. The efficiency is greatly improved when the units and storage that need to be dealt with areincreasing.

The cinema algorithm and the key change algorithm mentioned in the paper have some of the most basic concurrent algorithms that cannot be expressed by the sequential descriptive language. Under the combination of the two algorithms, sorting out the specific number of elements requires only two or three steps to finish the sorting, if it is done concurrently with relatively rich resources. Except for the second step in which a synchronic action of the whole is required, the concurrent treatments are used all the other time. In this way, the combined algorithms enjoy much more efficiency than that in the sequential comparison.

As we know, the trickiest problem in a system is not the one that happens regularly and frequently, but the one that occurs randomly and occasionally. If the system can be described in unambiguous formalization, then the problem cannot be solved. Corresponding to the sequential descriptive language, π calculus has great advantages in describing the concurrent mobile system that are quite popular nowadays. Still, although π calculus makes our expressions of concurrent events much more convenient, one has to be very careful in expressing them in order to reduce or even eliminate the randomness and instability outside the intention of modelingdesign.

Footnotes

Acknowledgments

The work has been funded by the Program of Critical Theories and Technological Researches on the New Information Network (SKLSE-2015-A-06) of the State Key Lab of Software Engineering, Computer School of Wuhan University, China.

References

Milner

, Communicating and Mobile Systems, the π-calculus.:, Cambridge, UK, Cambridge University Press, 1999.

Milner

, The polyadic-calculus: A tutorial, Logic and Algebra of Specification94 (1993), 91–180.

Milner

, The Polyadic π-Calculus: A tutorial, Theoretical Computer Science198 (1997), 239–249.

and Chen

, The comparison realization of the expressions based on π-calculus, Energy Education Science & Technology part A33 (2015), 1281–1296.

Liu

and Walker

, A Polymorphic Type System for the Polyadic pi-calculus. In Proceedings of the 6th International Conference on Concurrency Theory, Springer-Verlag, London, UK, 1995, pp. 103–116.

Hongye

, Veritfication on the Web Service Composition Based on Pi-Calculus, Graduation thesis Taiyuan University of Technology, 2008.

Xiaojuan

, The Expressiveness of π-Calculus via Programming, Dissertation Shanghai Jiao Tong University, 2009.

Kegang

and Xianglin

G.X.L.

, The Pi+ calculus - An extension of the Pi calculus for expressing petri nets, Chinese Journal of Computers34(2) (2011), 193–203.

Hui

, Yingyingm

and Zhiyong

, Modeling the mobile communication service based on PI-calculus, Journal on Communications30(4) (2009), 11–16.

10.

Yandong

, Research on formal verification of web services flow based on pi-calculus, Graduation thesis Zhejiang University, 2008.

11.

Pengwei

, WS-BPEL Modeling and Realization Based on π-Calculus, Graduation thesis Northwest University, 2009.

12.

Liu

and Lin

, A complete symbolic bisimulation for full applied pi calculus, Theoret Comput Sci458 (2012), 76–112.

13.

Dreier

, Ene

, Lafourcade

and Lakhnech

, On unique decomposition of processes in the applied pi-calculus, in: Proceedings of the 16th International Conference Foundations of Software Science and Computation Structures, FOSSACS’13, Rome, Italy, in: LNCS, vol. 7794, Sringer, 2013, pp. 50–64.

14.

Demangeon

and Honda

, Full abstraction in a subtyped pi-calculus with linear types, in: CONCUR, in: LNCS, vol. 6901, Springer-Verlag, 2011, pp. 280–296.

15.

Mostrousa

and Yoshidab

, Ession typing and asynchronous subtyping forthehigher-order π-calculus, Information and Computation241 (2015), 227–263.

16.

Dreier

, Ene

, Lafourcade

and Lakhnech

, On the existence and decidability of unique decompositions of processes in the applied π –calculus, Theoretical Computer Science612 (2016), 102–125.

17.

Lekshmy

V.G.

and Bhaskar

, Programming Smart Environments Using π-calculus Procedia Computer Science, Volume 46, 2015, pp. 884–891.

18.

Liu

, Wang

, He

, Li

and Liu

, Using pi-calculus to model web service interaction, Journal of Computational Information Systems (2013), 1759–1767.

19.

Nabih

A.K.

, Gomaa

M.M.

, Osman

H.S.

and Aly

G.M.

, Modeling, simulation, and control of smart homes using petrinets, International Journal of Smart Home5(3) (2011).

20.

Dreier

, Ene

, Lafourcade

and Lakhnech

, On the existence and decidability of unique decompositions of processes in the applied π–calculus, Theoretical Computer Science612 (2016), 102–125.

21.

Dreier

, Lafourcade

and Lakhnech

, Defining privacy for weighted votes, single and multi-voter coercion, in: Proceedings of the 17th European Symposium on Research in Computer Security, ESORICS’12, pisa, Italy, LNCS, vol. 7459, Springer, 2012, pp. 451–468.

22.

Dreier

, Ene

, Lafourcade

and Lakhnech