Using Central Nodes to Improve P System Synchronization

Using Central Nodes to Improve P System Synchronization Michael J. Dinneen, Yun-Bum Kim, and Radu Nicolescu Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand {mjd,yun,radu}@cs.auckland.ac.nz Summary. We present an improved solution for the Firing Squad Synchronization Problem (FSSP) for digraph-based P systems. We improve our previous FSSP algorithm by allowing the general to delegate a more central cell in the P system to send the final command to synchronize. With ebeing the eccentricity of the general and rdenoting the radius of the underlying digraph, our new algorithm guarantees to synchronize all cells of the system, between e+ 2r+ 3 steps (for all trees structures and many digraphs) and up to 3e+ 7 steps, in the worst case for any digraph. Empirical results show our new algorithm for tree-based P systems yields at least 20% reduction in the number of steps needed to synchronize over the previous best-known algorithm. 1 Introduction The Firing Squad Synchronization Problem (FSSP) is one of the best studied problems for cellular automata, originally proposed by Myhill in 1957 [11]. The initial problem involves finding a cellular automaton, such that after the “firing” order is given by the general, after some finite time, all the cells in a line enter a designated firing state, simultaneously and for the first time. For an array of length nwith the general at one end, minimal time (2n−2) solutions was presented by Goto [6], Waksman [18] and Balzer [2]. Several variations of the FSSP have been proposed and studied [12, 15]. The FSSP have been proposed and studied for variety of structures [10, 13, 7, 4]. In the field of membrane computing, deterministic solutions to the FSSP for a tree-based P system have been presented by Bernardini et al. [3] and Alhazov et al. [1]. For digraph-based P systems, we presented a deterministic solution in [5] for the generalized FSSP (in which the general is located at an arbitrary cell of the digraph), which runs in 3e+ 11 steps, where eis the eccentricity of the general. In this paper, we present an improved FSSP solution for tree-based P systems, where the key improvement comes in having the general delegate a more central cell, as an alternative to itself, to broadcast the final “firing” order, to enter the 126 M.J. Dinneen, Y.-B. Kim, R. Nicolescu firing state. We also give details on how to use this approach to improve the synchronization time of digraph-based P systems. It is well known in cellular automata [17], where “signals” with propagating speeds 1/1 and 1/3 are used to find a half point of one-dimensional arrays; the signal with speed 1/1 is reflected and meets the signal with speed 1/3 at half point. We generalize the idea used in cellular automata to find the center of a tree that defines the membrane structure of a P system. Let rdenote the radius of the underlying graph of a digraph, where e/2≤r≤e. Our new algorithm is guaranteed to synchronize in tsteps, where e+ 2r+ 3 ≤ t≤3e+ 7. In fact, the lower bound is achieved, for all digraphs that are trees. In addition to our FSSP solution, determining a center cell has many potential real world applications, such as facility location problems and broadcasting. The rest of the paper is organized as follows. In Section 2, we give some basic preliminary definitions including our P system model and formally introduce the synchronization problem that we solve. In Section 3, we provide a detailed P system specification for solving the FSSP for tree-based P systems. In Section 4, we provide a detailed P system specification for solving the FSSP for digraph-based P systems. Finally, in Section 5, we summarize our results and conclude with some open problems. 2 Preliminary We assume that the reader is familiar with the basic terminology and notations, such as relations, graphs, nodes (vertices), edges, directed graphs (digraphs), directed acyclic graphs (dag), arcs, alphabets, strings and multisets. For a digraph (X, δ), recall that Neighbor(x) = δ(x)∪δ−1(x). The relation Neighbor is always symmetric and defines a graph structure, which will be here called the virtual communication graph defined by δ. A special node g∈Xis designated as the general. For a given general g, we define the depth of a node x,depthg(x)∈N, as the length of a shortest path between gand x, over the Neighbor relation. Recall that the eccentricity of a node x∈X,ecc(x), as the maximum length of a shortest path between xand any other node. We note ecc(g) = max{depthg(x)|x∈X}. Recall that a (free or unrooted) tree has either one or two center nodes—any node with minimum eccentricity. We denote a tree T= (X, A), rooted at node g∈Xby Tg. The height of a node xin Tgis denoted by heightg(x). For a tree Tg, we define the middle node to be the center node closest to gof the underlying tree Tof Tg. Let Tg(x) denote the subtree rooted at node xin Tg. Given nodes xand y, if y∈Neighbor(x) and depthg(y) = depthg(x) + 1, then xis a predecessor of yand yis a successor of x. Similarly, a node zis a peer of x, if z∈Neighbor(x) and depthg(z) = depthg(x). Note that, for node x, the set of peers and the set of successors are disjoint with respect to g. For node x,Predg(x) = {y|yis a predecessor of x},Peerg(x) = {y|yis a peer of x}and Succg(x) = {y|yis a successor of x}. Using Central Nodes to Improve P System Synchronization 127 Definition 1. AP system of order nwith duplex channels and cell states is a system Π= (O, K, δ), where: 1. Ois a finite non-empty alphabet of objects; 2. K={σ1, σ2, . . . , σn}is a finite set of cells; 3. δis an irreflexive binary relation on K, which represents a set of structural arcs between cells, with duplex communication capabilities. Each cell, σi∈K, has the initial configuration σi= (Qi, si0, wi0, Ri), and the current configuration σi= (Qi, si, wi, Ri), where: •Qiis a finite set of states; •si0∈Qiis the initial state;si∈Qiis the current state; •wi0∈O∗is the initial content;wi∈O∗is the current content; note that, for o∈O,|wi|odenotes the multiplicity of object oin the multiset wi; •Riis a finite ordered set of multiset rewriting rules (with promoters) of the form: s x →αs0x0(u)β|z, where s, s0∈Q,x, x0, u ∈O∗,z∈O∗is the promoter [9], α∈ {min,max}and β∈ {↑,↓,l}. For convenience, we also allow a rule to contain zero or more instances of (u)β. For example, if u=λ, i.e. the empty multiset of objects, this rule can be abbreviated as s x →αs0x0. A cell evolves by applying one or more rules, which can change its content and state and can send objects to its neighbors. For a cell σi= (Qi, si, wi, Ri), a rule s x →αs0x0(u)β|z∈Riis applicable, if s=si,x⊆wi,z⊆wi,δ(i)6=∅for β=↓,δ−1(i)6=∅for β=↑and δ(i)∪δ−1(i)6=∅for β=l. The application of a rule transforms the current state sto the target state s0transforms multiset xto x0and sends multiset uas specified by the transfer operator β(as further described below). Note that, multisets x0and uwill not be visible to other applicable rules in this same step, but they will be visible after all the applicable rules have been applied. The rules are applied in the weak priority order [14], i.e. (1) higher priority applicable rules are applied before lower priority applicable rules, and (2) a lower priority applicable rule is applied only if it indicates the same target state as the previously applied rules. The rewriting operator α=max indicates that an applicable rewriting rule of Riis applied as many times as possible. The rewriting operator α=min indicates that an applicable rewriting rule of Riis applied once. If the right-hand side of a rule contains (u)β,β∈ {↑,↓,l}, then for each application of this rule, a copy of multiset uis replicated and sent to each cell σj∈δ−1(i) if β=↑,σj∈δ(i) if β=↓ and σj∈δ(i)∪δ−1(i) if β=l. All applicable rules are applied in one step. An execution of a P system is a sequence of steps, that starts from the initial configuration. An execution halts if no further rules are applicable for all cells. Problem 2. We formulate the FSSP to P systems as follows: Input: An integer n≥2 and an integer g, 1 ≤g≤n. Output: A class Cof P systems that satisfies the following two conditions for any 128 M.J. Dinneen, Y.-B. Kim, R. Nicolescu weakly connected digraph (X, A), isomorphic to the structure of a member of C with n=|X|cells. 1. Cell σgis the only cell with an applicable rule (i.e. σgcan evolve) from its initial configuration. 2. There exists state sf∈Qi, for all σi∈K, such that during the last step of the system’s execution, all cells enter state sf, simultaneously and for the first time. We want to find a general-purpose solution to the FSSP that synchronizes in the fewest number of steps, as a function of some of the natural structural properties of a weakly-connected digraph (X, A), such as the eccentricity of node g∈Xin the communication graph defined by A. 3 Deterministic FSSP solution for rooted trees We first solve Problem 2 for the subclass of weakly-connected digraphs (X, A), where the underlying graph of (X, A) is a tree. This section is organized as follow. In Section 3.1, we present the P system for solving the FSSP for trees rooted at the general. In order to help the comprehension of our FSSP algorithm, we provide a trace of the FSSP algorithm in Table 1. Phase I of our FSSP algorithm is described in Section 3.2, which finds the middle cell (i.e. a center of a tree, closest to the root) and determines the height of the middle cell. Phase II of our FSSP algorithm is described in Section 3.3, which broadcasts the “command” that prompts all cells to enter the firing state. Finally, in Section 3.4, we present some empirical results that show improvements of our algorithm over the previously best-known FSSP algorithms for tree-based P systems [1, 5]. 3.1 P systems for solving the FSSP for rooted trees Given a tree (X, A) and g∈X, our FSSP algorithm is implemented using the P system Π= (O, K, δ) of order n=|X|, where: 1. O={a, b, c, e, h, o, v, w}. 2. K={σ1, σ2, . . . , σn}. 3. δis a rooted tree, with an underlying graph isomorphic to (X, A), where the general σg∈K(the root of δ) corresponds to g∈X. All cells have the same set of states, the same set of rules and start at the same initial quiescent state s0, but with different initial contents. The first output condition of Problem 2 will be satisfied by our chosen set of rules. For each cell σi∈K, its initial configuration is σi= (Q, s0, wi0, R) and its final configuration at the end of the execution is σi= (Q, s6,∅, R), where: •Q={s0, s1, s2, s3, s4, s5, s6}, where s0is the initial quiescent state and s6is the firing state. Using Central Nodes to Improve P System Synchronization 129 •wi0={o}if σi=σg, ∅if σi6=σg. •Ris defined by the following rulesets. Rules used in Phase I: all the rules in states s0,s1,s2,s3and rule 4.6 in state s4. Rules used in Phase II: all the rules in states s4and s5, except rule 4.6. 0. Rules in state s0: 1. s0o→max s1ahou (b)↓ 2. s0b→max s1ah (e)↑(b)↓ 3. s0b→max s4a(ce)↑ 1. Rules in state s1: 1. s1a→max s2ah 2. Rules in state s2: 1. s2aaa →max s4a 2. s2aa →max s3a 3. s2ceu →max s2 4. s2ce →max s2 5. s2aee →max s2aeeh 6. s2aeooo →max s2aa (o)↓ 7. s2aeou →max s2aa (o)↓ 8. s2aeo →max s2aehoo 9. s2ao →max s2aaa 10. s2ae →max s2aeh 11. s2a→max s2aa (c)↑ 12. s2u→max s2 3. Rules in state s3: 1. s3a→max s4a 2. s3h→max s4 4. Rules in state s4: 1. s4hh →max s5w(v)l 2. s4avv →max s5aw (v)l 3. s4avv →max s5aw 4. s4av →max s6 5. s4v→max s5w(v)l 6. s4o→max s4 5. Rules in state s5: 1. s5aww →max s5aw 2. s5aw →max s6 3. s5v→max s6 4. s5o→max s6 σ1 σ2σ3 σ4σ5 σ6σ7 σ8σ9 σ10 σ11 σ1 σ2σ3 σ4σ5 σ6σ7 σ8σ9 σ10 (a) (b) Fig. 1. (a) a tree with the center σ5; (b) a tree with two centers σ3and σ5,σ3being the middle cell. 130 M.J. Dinneen, Y.-B. Kim, R. Nicolescu Table 1. The traces of the FSSP algorithm on a P system with the membrane structure defined by the tree shown in Figure 1 (a), where the general is σ1and the middle cell is σ5. The step in which the Phase I ends (or the Phase II begins) is indicated by the shaded table cells. Step σ1σ2σ3σ4σ5σ6σ7σ8σ9σ10 σ11 0s0o s0s0s0s0s0s0s0s0s0s0 1s1ahou s0b s0b s0s0s0s0s0s0s0s0 2s2ace2h2ou s4a s1ah s0b s0b s0s0s0s0s0s0 3s2aeh3o2s4a s2ae2h2s1ah s1ah s0b s0b s0s0s0s0 4s2aeh4o3s4a s2ae2h3s2aeh2s2aeh2s1ah s1ah s0b s0b s0s0 5s2a2h4s4ao s2ae2h4o s2aeh3s2aeh3s2aceh2s2aeh2s4a s1ah s0b s0 6s3ah4s4a s2ae2h5o s2aceh4s2aeh4s2a2h2s2aeh3s4a s2aeh2s1ah s0b 7s4a s4a s2ace2h6o s2a2h4s2aeh5s3ah2s2aeh4s4a s2aeh3s2aceh2s4a 8s4a s4a s2aeh7o2s3ah4s2aeh6s4a s2aeh5s4a s2aceh4s2a2h2s4a 9s4a s4a s2aeh8o3s4a s2aeh7s4a s2aceh6s4a s2a2h4s3ah2s4a 10 s4a s4a s2a2h8s4ao s2aceh8o s4a s2a2h6s4a s3ah4s4a s4a 11 s4a s4a s3ah8s4a s2a3h8s4a s3ah6s4a s4a s4a s4a 12 s4a s4a s4a s4a s4ah8s4a s4a s4a s4a s4a s4a 13 s4a s4a s4av4s4a s5aw4s4a s4av4s4a s4a s4a s4a 14 s4av3s4a s5aw3s4av3s5av6w3s4a s5aw3s4a s4av3s4a s4a 15 s5aw2s4av2s5av4w2s5aw2s5av6w2s4av2s5av2w2s4a s5aw2s4av2s4a 16 s5avw s5aw s5av4w s5avw s5av6w s5aw s5av2w s4av s5avw s5aw s4av 17 s6s6s6s6s6s6s6s6s6s6s6 Using Central Nodes to Improve P System Synchronization 131 3.2 Phase I: Find the middle cell of rooted trees In this phase, a breadth-first search (BFS) is performed from the root, which propagates symbol bfrom the root to all other cells. When the symbol bfrom the BFS reaches a leaf cell, symbol cis reflected back up the tree. Starting from the root, the search for the middle cell is performed as described below, where symbol orepresents the current search pivot. Note that symbol o’s propagation speed is 1/3 of the propagation speed of symbols band c; intuitively, this ensures that o and cmeet in the middle cell. We provide a visual description of the propagations of symbols b,cand oin Figure 4 (for a tree with one center) and Figure 3 (for a tree with two centers). Details of Phase I Objective: The objective of Phase I is to find the middle cell, σm, and its height, heightg(m). Precondition: Phase I starts with the initial configuration of P system Π, described in Section 3.1. Postcondition: Phase I ends when σmenters state s4. At the end of Phase I, the configuration of cell σi∈Kis (Q, s4, wi, R), where |wi|a= 1; |wi|h= 2·heightg(i), if σi=σm. Description: In Phase I, each cell starts in state s0, transits through states s1, s2, s3, and ends in state s4; a cell in state s4will ignore any symbol othat it may receive. The behaviors of cells in this phase are described below. •Propagation of symbol b:The root cell sends symbol bto all its children (Rule 0.1). An internal cell forwards the received symbol bto all its children (Rule 0.2) After applying Rule 0.1 or 0.2, each of these non-leaf cells produces a copy of symbol hin each step, until it receives symbol cfrom all its children (Rules 1.1 and 2.10). •Propagation of symbol c:If a leaf cell receives symbol b, then it sends symbol cto its parent (Rule 0.3) and enters state s4(the end state of Phase I). If a non-leaf cell receives symbol cfrom all its children, then it sends symbol c to its parent (Rules 2.4 and 2.11), consumes all copies of symbol hand enters state s4(Rule 3.2). •Note, when a cell applies Rule 0.2 or 0.3, it sends one copy of symbol eup to its parent. A copy of symbol eis consumed with a copy of symbol cby Rule 2.4. Hence, |wi|e=kindicates the number of σi’s children that have not sent symbol cto σi. •Propagation of symbol o:The root cell initially contains the symbol o. We denote σjas the current cell that contains symbol oand has not entered state s4. Assume, at step t,σjreceived symbol cfrom all but one subtree rooted at σv. Starting from step t+ 1, σjproduces a copy of symbol oin each step, until it 132 M.J. Dinneen, Y.-B. Kim, R. Nicolescu receives symbol cfrom σv(Rule 2.8), That is, |wj|o−1 indicates the number of steps since σjreceived symbol cfrom all of its children except σv. If σjreceives symbol cfrom σvby step t+ 2, i.e. |wj|o≤3, then σjis the middle cell; σjkeeps all copies of symbol hand enters state s4(Rule 2.1). Otherwise, σjsends a copy of symbol oto σvat step t+ 3 (Rule 2.6 or 2.7); in the subsequent steps, σjconsumes all copies of symbol hand enters state s4(Rules 2.2 and 3.2). Note, using current setup, σjcannot send a symbol to a specific child; σjhas to send a copy of symbol oto all its children. However, all σj’s children, except σv, would have entered state s4. Proposition 1 indicates the step in which σmreceives symbol cfrom all its children and Proposition 2 indicates the number of steps needed to propagate symbol ofrom σgto σm. Proposition 1. Cell σmreceives the symbol cfrom all its children by step heightg(g)+ heightg(m). Proof. Cell σmis at distance heightg(g)−heightg(m) from σg, hence σmreceives symbol bin step heightg(g)−heightg(m). In the subtree rooted at σm, the propagations of the symbol bfrom σmto its farthest leaf and the symbol c reflected from the leaf to σmtake 2 ·heightg(m) steps. Thus, σmreceives symbol cfrom all its children by step heightg(g)−heightg(m) + 2 ·heightg(m) = heightg(g) + heightg(m). ut σm σg w x z σi σ1σ2σk (a) (b) Tm(1) Tm(2) Tm(k) σm 1 Fig. 2. (a) ksubtrees of σm,Tm(1), Tm(2),...,Tm(k). (b) The structure of subtree Tm(j), which contains σg. Proposition 2. The propagation of the symbol ofrom σgto σmtakes at most heightg(g) + heightg(m)steps. Proof. For a given tree Tg, rooted at σg, we construct a tree Tm, which re-roots Tgat σm. Recall, Tm(i) denotes a subtree rooted at σiin Tm. Assume that σmhas k≥2 subtrees, Tm(1), Tm(2), . . . , Tm(k), such that heightm(1) ≥heightm(2) ≥ Using Central Nodes to Improve P System Synchronization 133 · · · ≥ heightm(k) and heightm(1) −heightm(2) ≤1. Figure 2 (a) illustrates the subtrees of σm. Assume Tm(i) is a subtree of σm, which contains σg. In Tm(i), let zbe the height of σgand x+w≥0 be the distance between σgand σi. Figure 2 (b) illustrates the z,xand win Tm(i). In Tm(i), let pbe a path from σito its farthest leaf and tbe the number of steps needed to propagate symbol ofrom σgto σm. Note, heightm(m) = heightg(m) and x+w+ 1 = heightg(g)−heightg(m). We have three cases to consider to prove Proposition 2. 1. heightm(i) = heightm(m)−1. •If σgis a part of path p, then z+x+w+ 1 = heightm(m), hence 2z+ 3(x+w+ 1) = 2(z+x+w+ 1) + (x+w+ 1) = 2 ·heightm(m)+(heightg(g)−heightg(m)) =heightg(g) + heightg(m) •If σgis not a part of p, then (v−w) + w+ 1 = v+ 1 = heightm(m), hence x+ 2(v−w) + 3(w+ 1) = 2(v+ 1) + (x+w+ 1) = 2 ·heightm(m)+(heightg(g)−heightg(m)) =heightg(g) + heightg(m) Cell σmreceives symbol oin step heightg(g) + heightg(m). 2. heightm(i) = heightm(m)−2. •If σgis a part of p, then z+x+w+ 1 = heightm(m)−1, hence 2z+ 3(x+w+ 1) = 2(z+x+w+ 1) + (x+w+ 1) = 2 ·heightm(m)−2 + heightg(g)−heightg(m) =heightg(g) + heightg(m)−2 •If σgis not a part of p, then (v−w) + w+ 1 = v+ 1 = heightm(m)−1, hence x+ 2(v−w) + 3(w+ 1) = 2(v+ 1) + (x+w+ 1) = 2 ·heightm(m)−2 + heightg(g)−heightg(m) =heightg(g) + heightg(m)−2 Note, symbol oremains in σmfor at least two steps. Thus, symbol o, arrived in σmat step heightg(g) + heightg(m)−2, will remain in σmuntil step heightg(g) + heightg(m). 3. heightm(i) = heightm(m)−j,j≥3. 140 M.J. Dinneen, Y.-B. Kim, R. Nicolescu to the uniform randomness of the labeled tree generator, we assumed the general is placed at the node labeled by 1. Each row in Table 3 is based on 100 random trees of that given order. We have run both test suites several times and the results are consistent with these two tables. Hence, we are pretty confident in the practical speedup that our new synchronization algorithm provides. Table 3. Statistics for improvement on random trees of various (larger) orders. avgerage avgerage avgerage % ndiameter radius eccentricity gain gain 1000 21 11 16.27 10.54 21.59 2000 32 16 23.45 14.90 21.18 3000 26 13 19.97 13.95 23.27 4000 30 15 22.65 15.30 22.51 5000 35 18 26.51 17.01 21.40 6000 32 16 23.82 15.64 21.89 7000 34 17 25.29 16.58 21.85 8000 34 17 25.01 16.03 21.36 9000 40 20 28.37 16.74 19.67 10000 37 19 27.16 16.32 20.03 10000 38 19 27.36 16.72 20.37 20000 37 19 28.23 18.47 21.80 30000 43 22 31.74 19.49 20.46 40000 43 22 31.55 19.09 20.18 50000 42 21 30.81 19.63 21.23 60000 44 22 32.50 21.00 21.54 70000 48 24 34.55 21.09 20.35 80000 45 23 33.08 20.17 20.32 90000 50 25 36.00 22.01 20.37 100000 47 24 34.15 20.29 19.81 4 FSSP solution for digraphs The key idea of FSSP solution for digraphs is as follows. For a given digraph, perform a BFS from the general on the communication graph and construct a virtual spanning tree, implemented via pointer symbols, not by changing existing Using Central Nodes to Improve P System Synchronization 141 arcs. If a node finds multiple parents in the BFS, then one of the parents is chosen as its spanning tree parent. In Figure 6, (a) illustrates a digraph G, (b) illustrates the underlying graph of Gand (c) illustrates a spanning tree of the underlying graph of G, rooted at σ1. Using the spanning tree constructed from the BFS, the FSSP algorithm described in Section 3, is applied to achieve the synchronization. We present the details of P system for solving the FSSP (Problem 2) for digraphs in Section 4.1. A trace of the FSSP algorithm for digraphs is given in Table 4. The details Phases I and II of this FSSP algorithm are described in Sections 4.2 and 4.3, respectively. Finally, in Section 4.4, we present some empirical results that illustrates expected improvements of our new algorithm over our previous FSSP algorithm for digraphs [5]. σ1 σ2 σ3 σ4 σ5 σ6 σ7 σ8 σ9 σ1 σ2σ3σ4 σ5σ6σ7 σ8 σ9 (a) (c) σ1 σ2σ3σ4 σ5σ6σ7 σ8 σ9 (b) Fig. 6. (a) A digraph G. (b) The underlying graph of G. (c) A spanning tree of the underlying graph of G, rooted at σ1. 4.1 P systems for solving the FSSP for digraphs Given a digraph (X, A) and g∈X, our FSSP algorithm is implemented using the P system Π0= (O, K, δ) of order n=|X|, where: 1. O={a, h, o, v, w, x, z}∪{ιk, bk, ck, ek, pk|1≤k≤n}. 2. K={σ1, σ2, . . . , σn}. 3. δis a digraph, isomorphic to (X, A), where the general σg∈Kcorresponds to g∈X. All cells have the same set of states and start at the same initial quiescent state s0, but with different initial contents and set of rules. The first output condition of Problem 2 will be satisfied by our chosen set of rules. In this FSSP solution, we extend the basic P module framework, described Section 2. Specifically, we assume that each cell σi∈Khas a unique cell ID symbol ιi, which will be used as an immutable promoter and we allow rules with a simple form of complex symbols. 142 M.J. Dinneen, Y.-B. Kim, R. Nicolescu To explain these additional features, consider rules 3.10 and 3.11 from the ruleset R, listed below. In this ruleset, symbols iand jare free variables (which in our case happen to match cell IDs). Symbols eiand ejare complex symbols. Rule 3.11 deletes all existing ejsymbols, regardless of the actual values matched by the free variable j. However, the preceding rule 3.10 fires only for symbols ei, with indices imatching the local cell ID, as required by the right-hand side promoter ιi. Together, rules 3.10 and 3.11, applied in a weak priority scheme, keep all symbols ei, with indices imatching the local cell ID, and delete all other symbols ej. For each cell σi∈K, its initial configuration is σi= (Q, s0, wi0, R) and its final configuration at the end of the execution is σi= (Q, s7,{ιi}, R), where: •Q={s0, s1, s2, s3, s4, s5, s6, s7}, where s0is the initial quiescent state and s7 is the firing state. •wi0={ιgo}if σi=σg, {ιi}if σi6=σg. •Ris defined by the following rulesets. Rules used in Phase I: all the rules in states s0,s1,s2,s3,s4and rules 5.5 and 5.6 in state s5. Rules used in Phase II: all the rules in states s5and s6, except rules 5.5 and 5.6. 0. Rules for cells in state s0: 1. s0o→min s1ao (xbi)l|ιi 2. s0x→min s1a(xbi)l|ιi 3. s0bj→max s1pj 1. Rules for cells in state s1: 1. s1apj→max s2apj(ej)l 2. s1a→max s2a 3. s1pj→max s2 2. Rules for cells in state s2: 1. s2a→max s3a 2. s2bj→max s3 3. s2x→max s3 3. Rules for cells in state s3: 1. s3aaa →max s5a 2. s3aa →max s4a 3. s3ciei→max s3|ιi 4. s3aoooei→max s3aa (o)l|ιi 5. s3aoeiei→max s3ahoeiei|ιi 6. s3aoei→max s3ahooei|ιi 7. s3ao →max s3aaa 8. s3aei→max s3aeih|ιi 9. s3apj→max s3aa (cj)l 10. s3ei→max s3ei|ιi 11. s3ej→max s3 12. s3pj→max s4 13. s3pj→max s5 4. Rules for cells in state s4: 1. s4a→max s5 2. s4h→max s5 3. s4cj→max s5 5. Rules for cells in state s5: 1. s5a→max s6a(z)l 2. s5hh →max s6w(v)l 3. s5zv →max s6a(z)l 4. s5v→max s6w(v)l 5. s5o→max s5 6. s5cj→max s5 6. Rules for cells in state s6: 1. s6aw →max s6a 2. s6a→max s7 3. s6z→max s7 4. s6v→max s7 Using Central Nodes to Improve P System Synchronization 143 Table 4. The traces of the FSSP algorithm on the digraph of Figure 6 (a), where the general is σ1and the middle cell is σ2. The step in which the Phase I ends (or the Phase II begins) is indicated by the shaded table cells. Step σ1σ2σ3σ4σ5σ6σ7σ8σ9 0s0ι1o s0ι2s0ι3s0ι4s0ι5s0ι6s0ι7s0ι8s0ι9 1s1ι1ao s0ι2b1x s0ι3b1x s0ι4b1x s0ι5s0ι6s0ι7s0ι8s0ι9 2s2ι1ab2b3b4ox3s1ι2ap1s1ι3ap1s1ι4ap1s0ι5b2x s0ι6b2b3x2s0ι7b3b4x2s0ι8s0ι9 3s3ι1ae3 1o s2ι2ab5b6p1x2s2ι3ab6b7p1x2s2ι4ab7p1x s1ι5ae1p2s1ι6ae2 1p2p3x s1ι7ae2 1p3p4x s0ι8b5b6b7x3s0ι9 4s3ι1ae3 1ho s3ι2ae2 2p1s3ι3ae2e4p1s3ι4ae4p1s2ι5ab8e1p2x s2ι6ab8e2 1p2x2s2ι7ab8e2 1p4x2s1ι8ae2 2e4p5p6p7x2s0ι9b8x 5s3ι1ac1e3 1h2o s3ι2ae2 2hp1s3ι3a2s3ι4ae4hp1s3ι5ae1e6p2s3ι6ac1e2 1e6p2s3ι7ac1e2 1e6p4s2ι8ab9e2 2e4p6x3s1ι9ae6p8 6s3ι1ae2 1h3o s3ι2ac2e2 2h2p1s4ι3ac4s3ι4ac4e4h2p1s3ι5a2s3ι6ac1e6hp2s3ι7a2c1s3ι8ac2c4e2 2e4e8p6s2ι9ae6p8 7s3ι1ac1e2 1h4o s3ι2ae2h3p1s5ι3s3ι4a2h2s4ι5a s3ι6ac1e6h2p2s4ι7ac2 1s3ι8ac2c4e8hp6s3ι9ae6p8 8s3ι1ae1h5o2s3ι2ae2h4p1s5ι3s4ι4ah2s5ι5s3ι6ac1e6h3p2s5ι7s3ι8ac2c4c8e8h2p6s3ι9a2 9s3ι1ae1h6o3s3ι2ae2h5p1s5ι3s5ι4s5ι5c6s3ι6ac1c6e6h4p2s5ι7c6s3ι8a2c2c4h2s4ι9ac6 10 s3ι1a2h6s3ι2ac2e2h6op1s5ι3c2o s5ι4o s5ι5s3ι6a2c1h4s5ι7s4ι8ac2 2c4h2s5ι9 11 s4ι1ah6s3ι2a3h6p1s5ι3s5ι4s5ι5s4ι6ac1h4s5ι7s5ι8s5ι9 12 s5ι1s5ι2ah6s5ι3s5ι4s5ι5s5ι6s5ι7s5ι8s5ι9 13 s5ι1v3z s6ι2aw3s5ι3s5ι4s5ι5v3z s5ι6v3z s5ι7s5ι8s5ι9 14 s6ι1aw2s6ι2av6w2z3s5ι3v4z2s5ι4v2z s6ι5aw2s6ι6aw2s5ι7s5ι8v4z2s5ι9 15 s6ι1av3wz3s6ι2av6wz3s6ι3a2w2s6ι4aw s6ι5av2wz2s6ι6av4wz4s5ι7v5z5s6ι8a2w2s5ι9v2z2 16 s6ι1av3z3s6ι2av6z3s6ι3a2z5s6ι4az5s6ι5av2z2s6ι6av4z4s6ι7a5s6ι8a2z7s6ι9a2 17 s7ι1s7ι2s7ι3s7ι4s7ι5s7ι6s7ι7s7ι8s7ι9 144 M.J. Dinneen, Y.-B. Kim, R. Nicolescu 4.2 Phase I: Find the middle cell of a BFS spanning tree For a given digraph-based P system, a (virtual) spanning tree is constructed by a standard BFS originated from the general, where the tree parent of each cell is one of its BFS parents (randomly chosen). Each cell keeps the track of its spanning tree parent and this is achieved by the use of cell IDs (unique identifier ID), e.g., iis the cell ID of σi. Details of Phase I Objective: The objective of Phase I is to find the middle cell, σm, and its height, heightg(m). Precondition: Phase I starts with the initial configuration of P system Π, described in Section 4.1. Postcondition: Phase I ends when σmenters state s5. At the end of Phase I, the configuration of cell σi∈Kis (Q, s5, wi, R), where |wi|ιi= 1; |wi|a= 1 and |wi|h= 2 ·heightg(i), if σi=σm. Description: We describe below the details of the BFS spanning tree construction and the propagation of the reflected symbol in the BFS tree. The symbol o, starting from the general, propagates from a tree parent to one of its children, as described in the FSSP solution for tree-based P systems (Section 3.2). Hence, the details of symbol opropagation are not given here. •The details of the BFS spanning tree construction: A BFS starts from the general. When the search reaches cell σi,σiwill send a copy of symbol bito all its neighbors (Rule 0.1 or 0.2). From the BFS, cell σireceives a copy of symbol bjfrom each σj∈Predg(i), where σjis a BFS dag parent of σi. Cell σitemporarily stores all of its BFS dag parents by transforming each received symbol bjto symbol pj(Rule 0.3). Note, σiwill also receive a copy of symbol bkfrom each σk∈Peerg(i)∪Succg(i); however, σiwill discard each received symbol bk. Each cell selects one of its BFS dag parents as its tree parent. If cell σi has chosen σjas its tree parent, then σiwill discards each pk, where σk∈ Predg(i)\ {σj}(Rule 1.3). Additionally, σiwill send a copy of symbol ejto all its neighbors, which will be discarded by all σi’s neighbors, except σj(Rule 1.1). Hence, in each cell σi, the multiplicity of symbol eiwill indicate the number of σi’s tree children and symbol pjwill indicate that σjis the tree parent of σi; also, symbol pjwill later be used to propagate the reflected symbol back up the tree. •The details of reflected symbol propagation: To replicate the propagation of a reflected symbol up the BFS tree, each internal cell of the BFS tree needs to check if the received a reflected symbol came from one of its BFS tree children. Using Central Nodes to Improve P System Synchronization 145 Let σibe a BFS tree child of σj, where |wi|ei= 0. Recall that, in such case, cell σicontains symbol pj, where the subscript jis the ID of its BFS tree parent, and σjcontains symbol ej, such that |wj|ejis the number of σj’s BFS tree children. Guided by symbol pj,σisends symbol cjto all its neighbors (Rule 3.9). Cell σjconsumes a copy of symbol ejwith a copy of symbol cjby Rule 3.3; σj cannot consume symbol ejwith symbol ck, where j6=k. If σjreceives symbol cjfrom all its BFS tree children, then all copies of symbol ejwill be consumed, i.e. |wj|ej= 0. Proposition 7 indicates the step in which the BFS reaches cell σiand σireceives symbol bjfrom each σj∈Predg(i). Proposition 8 indicates the step in which σi receives symbol eifrom its tree child. Proposition 7. Cell σireceives symbol bjfrom each σj∈Predg(i)at step depthg(i)and sends symbol bito all its neighbors at step depthg(i)+1. Proof. Proof by induction, on d=depthg(i)≥1. At step 1, the general σgsends symbol bgto all its neighbors by Rule 0.1. Hence, at step 1, each cell σkat depth 1 receives symbol bg. Then, at step 2, by Rule 0.2, σksends symbol bkto each of its neighbors. Assume that the induction hypothesis holds for each cell σjat depth d. Consider cell σiat depthg(i) = m+ 1 = depthg(j) + 1. By induction hypothesis, at step depthg(j) + 1, each σj∈Predg(i) sends symbol bjto all its neighbors. Thus, at step depthg(j) + 1 = depthg(i), σireceives symbol bj. At step depthg(i) + 1, by Rule 0.2, σisends symbol bito all its neighbors. ut Proposition 8. Cell σireceives a copy of symbol eifrom each of its tree children at step depthg(i)+3. Proof. Assume that cell σj∈Succg(i) has chosen σias its tree parent. From Proposition 7, cell σjreceives symbol biat step depthg(j) = depthg(i) + 1. According to the description, σjwill send symbol eiat step depthg(j) + 2. Thus, σi will receive symbol eiat step depthg(i) + 3. ut Remark 1. From Proposition 8, σireceives symbol eifrom its tree child at step depthg(i) + 3. If σidoes not receive symbol eiat step depthg(i) + 3, then σican recognize itself as a tree leaf and send a reflected symbol to its tree parent at step depthg(i) + 4. That is, once a leaf cell is reached by the BFS, it will take three additional steps to send reflected symbol to its tree parent. Recall, in the FSSP algorithm for tree-based P systems, a leaf cell sends reflected symbol to its parent, one step after reached by the BFS. Thus, this FSSP algorithm for digraph-based P systems takes three additional steps to send the reflected symbol than the FSSP algorithm for tree-based P systems. 146 M.J. Dinneen, Y.-B. Kim, R. Nicolescu 4.3 Phase II: Determine the step to enter the firing state Similar to the Phase II described in Section 3.3, the firing order is broadcasted from the middle cell σm. The order is paired with a counter, which is initially set to the eccentricity of σmand decrements by one in each step of this broadcast operation. Details of Phase II Objective: The objective of Phase II is to determine the step to enter the firing state, such that during the last step of Phase II, i.e. the system’s execution, all cells enter the firing state, simultaneously and for the first time. Precondition: Phase II starts with the postcondition of Phase I, described in Section 4.2. Postcondition: Phase II ends when all cells enter the firing state s7. At the end of Phase II, the configuration of cell σi∈Kis (Q, s7,{ιi}, R). Description: The order arrives in σi, along every shortest paths from σmto σi. Hence, to compute the correct step to enter the firing state, cell σidecrements, in each step, the sum of all received counter by the number of shortest paths from σmto σiand σienters the firing state if the sum of all received counter becomes 0. The number of shortest paths from σmto σiis determined as follows. Cell σm sends a copy of symbol z. Each cell σiforwards symbol z, received from each σj∈Predm(i). The number of shortest paths from σmto σiis the sum of all copies of symbol zthat σireceives from each σj∈Predm(i). Let tbe the the current counter and kbe the number of shortest paths from σm to the current cell. In the FSSP solution for tree-based P systems, the condition for entering the firing state in the next step is when t= 1 (note k= 1). However, the FSSP solution, as implemented in this section, cannot directly detect if t=k, since k≥1 Instead, a cell enters the firing state after t= 0 is detected. Thus, the FSSP algorithm for digraph-based P systems requires one additional step in Phase II. Theorem 4. The synchronization time of the FSSP solution for digraph-based P systems is ecc(g)+2·ecc(m)+7. Proof. This FSSP algorithm for digraph-based P systems requires four additional overhead steps than the FSSP algorithm for tree-based P systems. Three of these four overhead steps are described in Remark 1 and the remaining overhead step is mentioned in Section 4.3. ut We end this section with a comment regarding improving the communication requirements of our FSSP solution. Currently, there may be an exponential number of broadcast objects generated since a given cell currently receives a copy of the counter from every possible shortest path from the middle cell. We can reduce number of broadcasted counters from an exponential to a polynomial as follows. Assume that, a counter, sent or forwarded from a cell, is annotated with the cell’s ID. In Phase II, if a cell receives counter from its BFS tree neighbor (from a BFS Using Central Nodes to Improve P System Synchronization 147 tree child for cells on the path from the general to the middle cell, otherwise from its original BFS tree parent), then it broadcasts the reduced-by-one counter, now annotated with its own ID, to all its neighbors. The total number of steps of this revised algorithm would still be the same as given in Theorem 4. 4.4 Empirical results We also tested the improvement in running times over our previous FSSP algorithm on digraph-based P systems. The rate of improvement drops off as the number of edges increase over n−1, the size of trees of order n. But for several sparse digraph structured P systems the improvement is still worthwhile. We did two tests suites; one for relatively small digraphs (illustrated in Figure 7) and one for larger digraphs as shown in Table 5. The graphs used in our empirical tests were generated using NetworkX [8]. For the statistics given in Table 5, we first generated connected random graphs of order nand size m. We then averaged over all possible locations for the general node. To model the parallel nature of P systems, we needed to generate a random BFS tree originating at the general. This was created by first performing a BFS from the general to constructing the BFS dag then randomly picking (for each non-general node) one parent within the dag structure as the parent for the BFS tree. For this BFS tree, with edenoting the eccentricity of the general and rdenoting the radius of the BFS tree, the “average gain” is the average difference of 3e− (e+2r) and the “average % gain” is the average of the (3e−(e+2r))/(3e) values. From our empirical results, we can observe that the radius of the BFS spanning trees seems to be close to the actual radius of the given virtual communication graphs. For the statistics given in the three dimensional plots of Figure 7 (generated using Gnuplot [20]), we generated 100 random connected (n, m)-graphs, for each order n, 20 ≤n≤40, and size m= (n−1)+2k, where 0 ≤k≤20. Note, the integer value of 2krepresents the number of edges added to a tree. We then averaged over all possible general starting positions. The vertical axis is the average percentage speedup of our new algorithm over our previous synchronization algorithm. One can also observe from this plot, at least 20% improvements (i.e. reduction in number of steps needed to synchronize), is maintained for k= 0 (i.e. the graph is a tree). However, as the graphs become less sparse, the expected improvement drops to near zero, when as few as 40 edges are added to the trees. In general, for fixed k, the expected improvement in performance, for (n, n +k) digraphs slightly increases as nincreases. However, for fixed n, the expected improvement in performance drops drastically as kincreases. 148 M.J. Dinneen, Y.-B. Kim, R. Nicolescu Table 5. Statistics for reduction in number of steps needed to synchronize on a few random (n, m)-graphs. graph avg tree avgerage avgerage n m radius radius gain gain % 100 100 15 15.68 16.7 23.16 100 110 9 11.47 3.14 8.02 100 120 7 8.97 1.6 5.45 100 130 7 8.13 1.0 3.86 100 140 6 7.33 0.72 3.12 200 200 20 20.73 17.91 20.10 200 210 16 19.12 5.08 7.81 200 220 13 15.74 3.9 7.34 200 230 9 11.24 2.24 6.04 200 240 9 11.41 2.13 5.68 300 300 25 25.00 22.32 20.57 300 310 17 18.95 7.95 11.56 300 320 16 18.61 8.29 12.14 300 330 12 15.0 3.37 6.73 300 340 12 14.03 2.46 5.37 400 400 24 24.56 24.10 21.94 400 410 22 24.79 7.73 8.99 400 420 19 21.91 7.12 9.31 400 430 15 17.85 2.78 4.81 400 440 13 15.86 2.29 4.48 500 500 28 29.14 23.30 19.04 500 510 24 27.28 9.68 10.04 500 520 19 23.17 8.72 10.56 500 530 16 19.87 5.68 8.34 500 540 16 19.25 5.70 8.60 600 600 28 30.99 22.35 17.66 600 610 25 28.78 14.63 13.51 600 620 22 24.965 5.39 6.49 600 630 19 22.065 5.72 7.64 600 640 17 20.32 4.15 6.18 graph avg tree avgerage avgerage n m radius radius gain gain % 700 700 35 38.68 25.58 16.56 700 710 23 29.55 10.09 9.72 700 720 23 26.59 8.39 9.08 700 730 21 24.69 7.70 9.00 700 740 20 25.11 7.50 8.66 800 800 40 42.66 26.93 15.99 800 810 28 32.50 13.08 11.16 800 820 29 33.91 9.13 7.91 800 830 23 26.36 8.06 8.84 800 840 20 25.19 7.80 8.93 900 900 53 60.73 25.92 11.72 900 910 35 39.23 12.94 9.44 900 920 24 30.37 7.44 7.27 900 930 25 29.23 7.42 7.50 900 940 21 24.90 5.74 6.88 1000 1000 60 66.96 26.72 11.09 1000 1010 33 37.43 20.27 14.20 1000 1020 26 31.19 8.64 8.11 1000 1030 25 29.63 7.87 7.81 1000 1040 26 30.32 11.41 10.55 1000 1000 46 48.45 26.58 14.35 1000 1010 31 34.77 20.07 14.93 1000 1020 28 32.98 11.91 10.19 1000 1030 24 29.30 9.23 9.07 1000 1040 23 27.62 6.66 7.17 2000 2000 76 76.07 85.98 24.07 2000 2010 55 61.33 30.50 13.27 2000 2020 39 44.73 18.55 11.45 2000 2030 33 42.11 11.21 7.83 2000 2040 32 39.78 13.68 9.78 5 Conclusions and future works In this paper, we explicitly presented an improved solution to the FSSP for treebased P systems. We improved our previous FSP algorithm [5] by allowing the general to delegate a more central cell in the tree structure, as an alternative to itself, to send the final “firing” command. This procedure for trees-based P systems was extended to digraph-based P systems. Here we use a virtual spanning BFS tree (rooted at the general) in the digraph and use our tree-based middle-cell algorithm for that tree to improve the synchronization time. Alternatively, we would like to develop a way to compute a center of an arbitrary graph since the radius of the graph may be less than the radius of a particular BFS spanning tree. Thus this future work may possibly provide even more guaranteed improvements in synchronization time. We summarize our work as follows. With ebeing the eccentricity of the general and rdenoting the radius of the graph, where e/2≤r≤e, we note the radius r0 of the spanning BFS tree satisfies e/2≤r≤r0≤e. Thus, we have the following results: Using Central Nodes to Improve P System Synchronization 149 n k 0 5 10 15 20 25 %speedup 20 22 24 26 28 30 32 34 36 38 40 0 5 10 15 20 25 30 35 40 %speedup Fig. 7. Discrete 3-dimensional plot of expected synchronization improvements for a small range of random connected (n, m)-graph structures, with m= (n−1) + kedges. •If the membrane structure of a considered P system is a tree, then synchronization time is e+ 2r+ 3. •If the membrane structure of a considered P system is a digraph, then synchronization time tis e+ 2r+ 7 ≤t≤3e+ 7. Our empirical work shows that the radius of the BFS spanning tree is often as small as the radius of its host graph and we expect, more often than not, the synchronization time to be closer to e+ 2r+ 7 than to 3e+ 7 for arbitrary digraph-based P systems. Finally, we mention a couple open problems for the future. We would like a theoretical proof based on properties of random trees of why it seems that the our gain in performance is independent of the order of the trees considered. The current FSSP solution is designed for digraph-based P systems with duplex channels. Another remaining open problem is to obtain an efficient FSSP solution that synchronizes strongly connected digraphs using simplex channels. Acknowledgments The authors wish to thank Ionut¸-Mihai Niculescu for providing us with some early empirical statistics on random graphs and to acknowledge the University of Auckland FRDF grant 9843/3626216 to assist our research.