=Paper=
{{Paper
|id=Vol-2718/paper26
|storemode=property
|title=The Spanning-tree Algorithm and Generating a Membrane Structure
|pdfUrl=https://ceur-ws.org/Vol-2718/paper26.pdf
|volume=Vol-2718
|authors=Šárka Vavrečková
|dblpUrl=https://dblp.org/rec/conf/itat/Vavreckova20
}}
==The Spanning-tree Algorithm and Generating a Membrane Structure==
https://ceur-ws.org/Vol-2718/paper26.pdf
The Spanning-tree Algorithm and Generating a Membrane Structure
Šárka Vavrečková
Silesian University in Opava, Bezručovo nám. 13, Opava, Czech Republic,
sarka.vavreckova@fpf.slu.cz
Abstract: Many articles on membrane systems seek to the current revision is IEEE 802.1D-2004, reaffirmed in
minimize the number of membranes. But if these systems 2011 [2, 17].
were to be used for practical purposes, we may need a sys- The MST algorithm is one of the graph algorithms, and
tem with a large number of membranes – the proper ar- it is one of the most known greedy algorithms. Greedy al-
rangement of this structure would be very difficult. In this gorithms are heuristic problem-solving algorithms search-
paper, we propose a procedure inspired by the spanning- ing for locally optimal choices with the intent to discover
tree algorithm to help optimize a complex structure of a global optimum. More information is available at [6, 7].
membranes, independently of system rules. The paper [8] describes the implementation of Dijk-
stra’s algorithm (finding the shortest path in a graph) using
P system, which is closely related to the spanning-tree, but
1 Introduction
a membrane system is a tool there, not a target.
Membrane computing is a framework of parallel dis- A dynamic structure of membranes (P Systems with ac-
tributed processing introduced by Gheorghe Pǎun in 1998. tive membranes) is discussed in [13] or [4], but the pre-
Research in this area is ongoing and many different types sented structure was able to dissolve membranes and to
of membrane systems have emerged since then. Informa- divide a membrane into two successor membranes. Each
tion is available at [12, 14, 15, 16], or the bibliography at membrane has its polarization (electrical charge with val-
[18]. ues {−, 0, +}), and the polarization of a membrane can
The intent of Membrane computing is to abstract com- be changed as well. All changes of membranes are made
puting using hierarchies of membranes in living cells. using rules.
Since 2000, the term P Systems has been used for mathe- In this paper, we work with dynamics of membrane
matical models of membrane systems. structure in a slightly different manner. Changes in the
The minimum spanning tree (MST) for a given struc- membrane structure are not built in the rules of the mem-
ture (network) of nodes is a substructure of the form of brane system, but they are meta-rules used to pre-prepare
a tree with optimal paths leading from nodes to the root the structure of the system, which will then work accord-
node, while maintaining the established rules for relation- ing to its own rules.
ships between nodes, even when the structure is changed
(adding new nodes, removing them or changing properties
of connections). There are many applications of the MST 2 Analogy between Membrane Structure
algorithm in various areas – network design, network op- and Tree Structure
timization, maximum bottleneck paths, image processing,
grouping objects into clusters of similar objects, approx- The basis of membrane systems is a membrane structure
imation of some NP-hard problems (e.g. traveling sales- inspired by the structure of a biological cell. A membrane
person problem), etc., see [1]. can contain certain objects and/or other (nested) mem-
There are several algorithms to find the MST: Kruskal’s branes. Thus, there may be a parent-child relationship be-
algorithm, Prim’s algorithm, Boruvka’s algoritm, the algo- tween the membranes. Objects can be manipulated using
rithm in the STP protocol (Spanning-Tree Protocol). Some rules, in some membrane systems there are also rules for
of them are discused in [3, 7]. manipulating membranes.
We will deal with the algorithm implemented in STP, The membrane structure is strictly hierarchical, it can
because, in addition to mathematical representation, it is be represented by a sequence of nested brackets or dis-
well described in the form of code, although for the pur- played by a tree in which the parent-child relationship cor-
poses of computer networks, and standardized. The MST responds to the inner-outer membrane relationship. One
algorithm implemented in the STP protocol maintains a membrane (the skin) is the main one (it contains all
loop-free logical topology with network devices (Ethernet the others), the remaining membranes always have one
switches or bridges), keeping backup physical connections parental membrane in which they are contained. Analo-
that are immediately available in the event of a change in gously, the tree has one main (root) node, all other nodes
logical topology. STP was standardized as IEEE 802.1D, have exactly one parent node. The representation using a
Copyright ©2020 for this paper by its authors. Use permitted under tree intuitively leads to the possibility of using graph algo-
Creative Commons License Attribution 4.0 International (CC BY 4.0). rithms designed for graphs in the form of a tree.
'' $ $
1 ' $ is to receive a data unit called a frame from one port and
2 ' $
5
3 forward it to another port, behind which the target device
for the given frame is located.
& % In general, we find it useful when there are redundant
& % ' ' $ paths in a network. But if we create redundant paths in
' $ 6 $
4 7
the network of switches, we also create loops, which have
a negative impact on network operation (broadcast frames
intended for all nodes in the network flow by the network
& % & %
& & % & %%in multiple copies, we call it “broadcast storm” ). The
1
solution is to leave redundant paths at the physical level
Figure 1: Example of Membrane Structure (cables), but remove them at the logical level (communica-
tion) by blocking data communication on a given connec-
tion. In case that the active path stops to forward frames,
The membrane structure can be represented graphically one of the logicaly blocked paths whose physical connec-
using Venn diagrams, brackets, or a tree of nodes repre- tion exists will be activated.
senting membranes. The membrane structure presented In the case of switches, the entire process is directed by
in Figure 1 by Venn diagram is represented by the string the STP protocol, which implements the spanning-tree al-
[ [ [ ]3 [ ]4 ]2 [ ]5 [ [ ]7 ]6 ]1 , and by the tree of nodes shown gorithm. The purpose of this algorithm is to negotiate its
in Figure 2. position in the hierarchy when connecting the switch to
1 t
@
the network and to keep the hierarchy in optimal condi-
@ tion according to the general rules and set priorities when
2 t 5 t @t6 changing the network structure. Each node has assigned
@
@
its own priority (in a parent-child relationship, the parent
3 t @t4 t7 will have a smaller priority number). The algorithm does
not depend on the number of nodes, it runs in parallel at
Figure 2: Tree of nodes all nodes and affects the structure of the entire network at
the same time.
The membranes are identified by their labels. The mem- When designing a large membrane structure, for each
brane structure presented in Figures 1 and 2 uses simple membrane we usually have an idea of how deep in the
numbers as labels. structure it should be roughly, and also which membranes
There are many articles and procedures that deal with are considered parental for it. We want to choose one of
the rules and objects in the membrane structure, but the the potential parents for the given membrane in the opti-
membranes themselves are supposed to be “somehow mization process as the parent membrane, and thus actu-
designed”, their structure is not usually specifically ad- ally include the given membrane into the structure (both
dressed. It is not necessary for a few membranes; however, the membrane and the tree structure). We can solve the
if this structure is to be large and very complex (which can choice of the main membrane or the root node of the tree
happen, for example, in a structure for simulating the oper- for the whole system similarly.
ation of many mutually hierarchically arranged systems),
we may encounter problems in the design of such a struc-
3 Preliminaries
ture. In the case of a complicated structure, it may happen
that we do not correctly express suitable relationships be- 3.1 Membrane Structure and P Systems
tween membranes, analogously in the tree we do not cor-
rectly express parent-child relationships between nodes. We assume the reader to be familiar with the basics of the
A tool we use for the design of a membrane structure formal language theory and membrane computing. For
can allow input in the form of nested brackets or in graph- further details we refer to [10] and [16].
ical form. In brackets, we can get lost in small tens of The definition of P Systems follows, but only some parts
membranes, the graphic input is lucid only till a certain ex- of the definition are important for the purposes of this ar-
tent of the network: with tens to hundreds of membranes, ticle. Different types of P Systems have quite different
we can get lost here as well. Or defining parenthood in definitions, and the mechanism we present is applicable to
membranes can be manually challenging for larger struc- various types.
tures. Each membrane has its region: the space delimited by
In this paper, we propose an optimization process that the given membrane, all contained objects and subordinate
can help organize a very large membrane structure. The membranes (with their contained objects) are situated in
process remains laborious, but increases the probability of this region. The region of a membrane corresponds to the
obtaining a better optimized structure. subtree in the tree representation of the structure.
In local computer networks (LAN) we work with net- 1 The definition of broadcast storm can be found e.g. at https://
work devices of the type switch. The role of the switch www.techopedia.com/definition/6270/broadcast-storm.
Definition 1 ([15]). Let H be a set of labels. A P System BID can be represented by the vector
of a degree m, m ≥ 1, is a construct (priority ; deviceID)
or by concatenation of these numbers (i.e. a number),
Π = (V, T,C, µ, w1 , . . . , wm , (R1 , ρ1 ), . . . , (Rm , ρm ))
the priority is more significant item than deviceID,
where: • rootID is BID of the root node, so every node knows
(i) V is a nonempty alphabet, its elements are called ob- the root,
jects, • root path cost (sum of costs of all links on the way to
(ii) T is an output alphabet, T ⊆ V , the root),
(iii) C is a set of catalysts, C ⊆ V − T , • each port linked to a neighbor has its portID con-
sisting of two parts: port priority and port number
(iv) µ is a membrane structure consisting of m mem- (counted from 1), these two properties can be repre-
branes, the membranes are labeled by the elements sented by a vector or concatenation similarly to BID,
of H,
• each port has three additional features: role, current
(v) wi , 1 ≤ i ≤ m, are strings representing multisets over status, and cost of link.
V associated with the region of the i − th membrane
in µ, The port status is either forwarding (active) or blocking
(the full algorithm defines more than two port states, also
(vi) Ri , 1 ≤ i ≤ m, are finite sets of evolution rules asso- depending on the protocol version).
ciated with the region of the i − th membrane in µ; The port role is one of the following:
an evolution rule is a pair (u, v), also written u → v,
where • root port – the active port through which the path to
the root node leads (leading to the parent node),
• u is a string over V ,
• v = v0 or v = v0 δ , where v0 is a string over • designated port – the active port leading to one of the
ahere , aout , ain j a ∈ V, 1 ≤ j ≤ m , and δ is a child nodes (or leading to another subtree, blocked by
special symbol ∈ / V representing dissolution of the neighbor),
membrane, • alternate port – non-active (blocked) port.
(vii) ρi , 1 ≤ i ≤ m, is a partial order relation over Ri spec- The original algorithm distinguishes two types of blocked
ifying the priorities of the rules in Ri . ports (alternate or backup).
Details and examples can be found in [15].
Algorithm 1: Basic Structures and Functions
3.2 The Spanning-tree Algorithm node : BID (priority, label),
rootID (priority, label),
For the purposes of this article, we will simplify the orig- RPcost,
inal spanning-tree algorithm and list only those parts of it rootPortID, // portID of the root port
that we will use for operations with a membrane structure. // ports are indexed by portID:
The full algorithm can be found in [9] (multiple pages) and ports[] (role, state, cost,
certainly [2]. The presented algorithms are created loosely neighborBID, neighborPortID);
according to [9, 2, 5].
function node.init()
As mentioned above, the spanning-tree algorithm is the
begin
parallel algorithm working on nodes of a network, e.g. on
// Neighbors’ BIDs and their portIDs are
interconnected network switches. The goal is to transform
determined later from obtained BPDUs.
the network into a tree with one root node. The process of
// Setting port costs,...
transformation is called convergence.
self.IAmNewRoot(); // Defined in Algorithm 2.
The algorithm was originally intended for network de-
end
vices called bridge, so the term “bridge” also appears in
the following text. // No BPDU came from the neighbor for a hold
Assume a network of nodes (bridges, switches, mem- time: the link or the neighbor is inoperative.
branes,. . . ), interconnected in some manner. There can function node.noRespFromNeigh(recPortID)
be more than one path between some nodes, the structure begin
does not yet have the form of a tree, the convergence pro- if (recPortID = = self.rootPortID) then
cess is in progress. // The root port waiting in vain for a BPDU.
Every node keeps the following information: The root has become unavailable, maybe
• BID (Bridge ID) consisting of two parts: I am the new root.
self.IAmNewRoot();
– priority of the node, end
– unique deviceID, e.g. MAC address of a switch,
The port cost (or link cost, it should be the same value
Algorithm 2: Auxiliary functions
on the both sides of the link) is used to calculate the opti-
mal path over network. The faster the port/link, the lower function node.changeRootPort(newRootPortID,
this number (and better link). newPortRole)
begin
The representation of a node and its initialization can be
// rootPortID==0 would mean that I am the root
found in Algorithm 1.
if (self.rootPortID != 0) then
The nodes communicate with each other using BPDU
self.ports[self.rootPortID].state = blocking;
messages (Bridge Protocol Data Unit). BPDU is valid
self.ports[self.rootPortID].role =
only for one link and the corresponding ports, between
newPortRole;
two neighbors; it is not resent to another link, the neigh-
bor generates the own BPDUs for its links. Every BPDU end
contains, inter alia, the following information: self.rootPortID = newRootPortID;
self.ports[newRootPortID].state = blocking;
• BID of the sender, self.ports[newRootPortID].role = rootPort;
• rootID (BID of the node that is being considered root end
by the sender),
// Obtained info about new root or root path cost
• root path cost (cost of the path from the sender to the changed, do synchronization downwards.
root), function node.makeSync(sender)
• portID and cost of the port the BPDU is sent over, begin
• other information. // Only connected/used ports are processed:
foreach (port in self.ports) do
The neighbors know each other through the BPDUs, in- port.state = blocking;
cluding BIDs and portIDs, and the root path cost is calcu- self.ports[self.rootPortID].state = forwarding;
lated by adding the cost of the link to the root path cost self.ports[self.rootPortID].sendBPDU_agree();
info obtained from the neighbor. foreach (port in self.ports) do
There are several types of BPDUs: Proposal BPDU is if ((port.role = = designatedPort)
sent downwards to inform its child nodes about the root or (port.role = = alternatePort)) then
node, Agreement BPDU is sent upwards to agree with the port.sendBPDU_proposal() ;
proposed root setting (see Algorithm 4), and others which end
are not necessary for our purposes.
The BPDUs are also used as a keep-alive mechanism function node.IAmNewRoot()
between neighbor nodes and the neighbors inform each begin
other about their parameters (BIDs, port numbers, etc.). self.rootID = self.BID;
Presume a situation where a new node is added to the self.RPcost = 0;
network. This node first assumes that it is the root, and self.rootPortID = 0;
starts sending BPDUs with BID = rootID. All its ports have foreach (port in self.ports) do
the role DP (designated port). Its neighbors receive the port.role = designatedPort;
BPDU with this information and compare the reported port.state = blocking;
rootID with the stored value. There are two possibilities: port.sendBPDU_proposal();
end
1. the reported rootID is greater than the stored rootID
end
– the new node does not become the root,
2. the reported rootID is less than the stored rootID –
the new node becomes the root.
The function node.IAmNewRoot() in Algorithm 2 illus- If a node obtains a BPDU with the declared rootID less
trates this situation. (i.e. better) than its stored rootID, it updates the own struc-
tures and sends the BPDUs to all neighbors (except of the
Example 1. The numbers deviceID are usually MAC ad- original sender), so these neighbors learn the change, sub-
dresses. For demonstration reasons, we will use only sequently their neighbors learn the change, etc.
“small” numbers for the both priorities and deviceIDs. The root node has the root path cost = 0 for all its ports,
If a node has the stored rootID = (32 ; 56) and an- so the newly connected node (considering to be root) sends
other node is reporting rootID = (31 ; 82), the reported BPDUs with this value to its neighbors. Each receiving
node becomes the new root (the lower number of prior- neighbor adds the cost of the receiving port/link to the ob-
ity means precedence). But if another node later reports tained root path cost information (the first command of the
rootID = (31 ; 95), the reported node will not become the function node.getBPDU_proposal() in Algorithm 3). The
root (its priority is the same as the root priority, but its next step depends on which port the BPDU came over. The
deviceID is greater, which means no precedence). first part of Algorithm 3 (the first “if” command block) il-
Algorithm 3: Getting BPDU: Proposal
// BPDU of the type “Proposal” received on the port “recPortID” from the given “sender” node.
function node.getBPDU_proposal(recPortID, sender)
begin
refRPcost = sender.RPcost + self.ports[recPortID].cost; // Root path cost from sender + cost between us
self.ports[recPortID].neighborBID = sender.BID; // Discovering neighbor’s BID
self.ports[redPortID].neighborPortID = sender.portID;
if (self.ports[recPortID].role = = rootPort) then // Info originated from the root port is trusted.
if ((sender.rootID < self.rootID) or ((sender.rootID = = self.rootID) and (refRPcost != self.RPcost))) then
// Path to the root has changed, but the direction remains.
self.ports[self.rootPortID].state = blocking; // blocking before any change of ports
self.rootID = sender.rootID;
self.RPcost = refRPcost;
self.makeSync(sender); // including sending BPDU Agreement upwards and Proposal downwards
else if (sender.rootID > self.BID) then // The root has become unavailable, maybe I am the new root.
self.IAmNewRoot()
return;
end
if (sender.rootID < self.rootID) then // New root notified, the reported rootID is better than I know:
self.changeRootPort(recPortID, designatedPort); // The receiving port becomes my new root port.
self.rootID = sender.rootID;
self.RPcost = refRPcost;
self.makeSync(sender);
else if (sender.rootID = = self.rootID) then
// The same root, maybe some other change – root path cost or direction?
if (refRPcost < self.RPcost) then // The root path cost has changed to a better value:
changeRootPort(recPortID, designatedPort);
self.RPcost = refRPcost;
self.makeSync(sender);
else if (refRPcost > self.RPcost) then // The root path cost has changed to a worse value:
if (sender.BID > self.BID) then // The sender is either under me or inside another subtree
self.ports[recPortID].role = designatedPort; // previously could have been alternatePort
self.makeSync(sender);
else // means: (sender.BID < self.BID), the sender is above me or inside another subtree
self.ports[recPortID].state = blocking;
self.ports[recPortID].role = alternatePort;
end
else // The same root and root path cost, but from different direction, choosing more eligible parent:
if (sender.BID > self.ports[rootPortID].neighborBID) then // The present parent is better, no change.
self.makeSync(sender);
else if ((sender.BID < self.ports[rootPortID].neighborBID)
or ((sender.BID = = self.ports[rootPortID].neighborBID)
and (self.ports[recPortID].neighborPortID < self.ports[rootPortID].neighborPortID))) then
// The potential new parent has better BID, changing the root port:
foreach (port in self.ports) do if (port.role = = alternatePort) then port.role = designatedPort ;
self.changeRootPort(recPortID, alternatePort);
foreach (port in self.ports) do if (port.role = = designatedPort) then
port.state = blocking;
port.sendBPDU_proposal();
end
end
end
end
end
lustrates the case for the root port of the node, while the 4 Optimization of Membrane Structure
next code represents the case for designated and alternate
ports. The algorithm can be run over an existing graph from
The node considers the reported rootID, root path cost which we want to create a tree, or individual elements
and other parameters to decide the best direction to the root (membranes) can be added gradually.
and the corresponding port roles. If the BPDU with the Consider a set of membranes, each of them has
correct rootID and the same lowest root path cost comes • contained objects, properties, functions, rules, etc.,
to more than one port (and therefore it is not possible to according to the type of membrane system,
select the root port according to the above procedure), the • its own identifier (label) and priority (i.e. BID); the
lower sender BID decides. If the sending nodes have the priority is added as metainformation for the purposes
same BID (e.g. when two or more parallel links lead be- of the algorithm,
tween two nodes), the portIDs of the sender’s port and the • the identifier and priority of the root membrane (skin;
neighbor’s port leading to current root are compared and i.e. rootID); it will probably be appropriate to deter-
the port with the neighbor’s lower portID is selected as the mine the skin membrane in advance and assign it the
root port. lowest BID number directly,
The configured ports are in the blocking state during
• ports to several possible neighbors in the membrane
determining port roles.
structure (potential parents and children) – links (re-
The both the reported rootID and the root path cost to- lations) to them, for each port we need its portID,
gether flood in all directions from the root node: first to the neighbor BID and the portID for the link on the
its neighbors (they count the cost of the link leading to the neighbor’s side, each such link is evaluated by cost as
root plus zero), then to their neighbors (the value increases metainformation.
again, they add the cost of the link to the obtained value),
etc. Each node gets the necessary information gradually, There may be left default values for added properties, or
the topology may change several times during the conver- we can set them manually to impact the resulting structure.
gence; when a node detects a root change, it communi- To make the procedure as illustrative as possible, we
cates information about the new root to its ports (except use the representation of the membrane structure in the
the root port) during the synchronization process (the func- form of a tree. The procedure described in Algorithms
tion node.makeSync(sender), see Algorithm 2). 1, 2, 3, and 4, is intended for network devices (however,
very simplified), but we can use this simplified version for
Whenever there is a change in the structure, in the prior-
membranes and just modify the terms.
ities of nodes or ports, etc., this procedure starts again and
Algorithm 5 is created by modifying Algorithm 1, the
the whole network gradually converges. If a node finds out
remaining algorithms can be modified in a similar way.
about the change:
The port priorities are not necessary (we need just port la-
• it evaluates the change reported in the BPDU pro- bels as portIDs), because we do not assume multiple con-
posal, nections between two membranes.
• if the node agrees, it changes its configuration and
sends back the BPDU agreement, Example 2. Let us demonstrate the above outlined pro-
• it blocks the ports to other neighbors and sends them cedure. For the sake of clarity, the individual membranes
the BPDU proposal. are created sequentially, but we would achieve the same
result even if all membranes were created in parallel or
In case that a neighbor agrees, it sends back the BPDU when the order was changed, only the convergence pro-
agreement (the port leading to this neighbor is activated cess would pass in different timing. The following initial
with the role “designated”). If it does not agree, it sends structure is given:
back the own proposal in the BPDU proposal.
3t.1 .2 2t.1 .1 1t.3 .1 6t
cost=15 .3 cost=10 .2 cost=8 .2
.2@
@ cost cost cost
co
Algorithm 4: Getting BPDU: Agreement
st=
@ =10 =12 =16
12
@ .2 .1 .2
// BPDU “Agreement” received on the port @t cost=8 t cost=10 t
.1
“recPortID”, my proposal is accepted by the 4 .3 .2 5 .3 .1 7
neighbor
function node.getBPDU_agree(recPortID) Figure 3: Initial structure for Example 2
begin
self.ports[recPortID].role = designatedPort; There are 7 membranes with connections and link costs,
self.ports[recPortID].state = forwarding; the ports are marked in a smaller font and with a point, e.g.
end the membrane no. 3 has the ports 3.1 (leading to the mem-
brane no. 2) and 3.2 (leading to the membrane no. 4). All
Algorithm 5: Base for Membranes • the membrane no. 5 is created, connected to no. 1 and
membrane: BID (priority, label), 4; considered to be the root (sending Proposal), but
rootID (priority, label), RPcost, receives back the message from the neighbors with
rootPortID, the lower rootID (sending back Agreement), the root
ports[] (role, state, cost, is no. 1; the root path cost from no. 1 is better (0 +
neighborBID, neighborPortID); 12), so the port 5.1 gets the role RP, the port 5.2 gets
th role AP, the opposite port 4.3 gets the role DP,
function membrane.create(BID, neighs[], costs[]) • the membrane no. 4 found an alternative path to the
begin root (no. 1) through no. 5 with the same root path
self.BID = BID; cost; but the neighbor no. 2 has better BID, so the
int c = neighs.count; root port remains,
if c > 0 then 1 t
for (int i = 1; (i <= MaxPorts) and (i <= c); @
i++) do @
self.ports[i].neighborBID = neighs[i]; 2 t 5 t @t6
self.ports[i].cost = costs[i]; @ @
... ; // according to implementation
@ @
3 t @t4 @t7
end
self.IAmNewRoot();
Figure 4: Modified structure (tree) for Example 2
end
• the membrane no. 6 is created, connected to no. 1, af-
function membrane.noRespFromNeigh(recPortID)
ter exchanging messages the root is no. 1, the port 6.1
begin
gets the role RP,
if (recPortID = = self.rootPortID) then
self.IAmNewRoot(); • the membrane no. 7 is created, connected to no. 5 and
end 6, after exchanging messages the root is no 1, the port
7.1 gets the role RP (the root path cost through no. 5
is better), the opposite port 5.3 gets the role DP, the
port 7.2 gets the role AP and the opposite port 6.2
membranes have the same priority: only labels are used gets the role DP.
to make decisions when comparing BIDs. This structure is
not in the form of tree, so we apply the transformation. Example 3. Setting various membrane priorities and dif-
Assume that the structure is formed gradually, for ex- ferent link costs causes the topology change. Let us take
ample from lower labels till larger labels (but the order is the previsous example and set the priority of the membrane
not important). The steps are as follows: no. 2 to 100, the others to 200, and change the cost of the
link between membranes no. 6 and 7 to the value 8.
• the membrane no. 1 is created, it is the root (the skin
membrane), all its ports have the role DP, (200,3) (100,2) (200,1) (200,6)
t.1 .2 t.1 .1 t.3 .1 t
• the membrane no. 2 is created and connected to the cost=15 .3 cost=10 .2 cost=8 .2
.2@
membrane no. 1; considered to be the root (sending @ cost cost cost
co
Proposal), but receives the message from no. 1 with
st=
@ =10 =12 =8
12
the lower (i.e. better) rootID (so sending back Agree- @ .2 .1 .2
ment), the root is no. 1, the port gets the role RP, @t cost=8 t cost=10 t
.1
.3 .2 .3 .1
• the membrane no. 3 is created, connected to no. 2; (200,4) (200,5) (200,7)
considered to be the root (sending Propossal), but Figure 5: Initial structure for Example 3
receives back the message from no. 2 with the lower
rootID (sending back Agreement), the root is no. 1,
As we can see (Figure 6), the structure has changed
the port 3.1 gets the role RP,
quite a lot.
• the membrane no. 4 is created, connected to no. 2 and 2 t
no. 3; considered to be the root (sending Proposal), @
but receives back the message from no. 2 and 3 with @
the lower rootID (sending back Agreement), the root 3 t 4 t @t1
is no. 1; the root path cost through no. 2 is 10 + 10 =
20, through no. 3 is 10 + 15 + 12 = 37, so the port 4.2 5 t 6 t t7
gets the role RP, the port 4.1 gets the role AP (because
sender.BID < self.BID), the port 3.1 of the membrane Figure 6: Modified structure (tree) for Example 3
no. 3 goes to the role DP,
5 Conclusions [7] Greenberg, H.J.: Greedy Algorithms for Minimum Span-
ning Tree [online]. Univeristy of Colorado (1998), online
The aim of this work is not to design a comprehensive tool available at http://glossary.computing.society.
for simulation of P systems, there is not enough space for informs.org/notes/spanningtree.pdf (Accessed
that. The goal is only to design a procedure for generating June 4, 2020)
suitable input, e.g. for P-Lingua type languages[11]. [8] Guo, P., Quan, Ch., Ye, L.: UPSimulator: A general P sys-
Membrane systems can be used to simulate complex tem simulator. Knowledge-Based Systems, vol. 170, 2019,
(real) systems with many relations. Real systems are be- pp. 20–25. ISSN: 0950-7051.
ing changed over time (not only by deleting existing mem- [9] Hewlett Packard Enterprise: Calculation process of the
branes) and the proposed procedure offers a way of repre- STP algorithm [online]. HPE FlexNetwork LAN Switch-
senting mutual relations that can be dynamically adapted. ing Configuration Guide (2017), online available at
The two examples show the consequences for the https://techhub.hpe.com/eginfolib/networking/
change in the membrane structure caused by the interven- docs/switches/7500/5200-1938a_l2-lan_cg/
content/495503520.htm (Accessed June 11, 2020)
tion in only two parameters – the priority of one membrane
and the cost of one link (relation). [10] Hopcroft, J.E., and Ullman, J.D.: Introduction to Au-
tomata Theory, Languages and Computation. Addison-
There is only one problem left to solve: if there are sev-
Wesley, 1979.
eral potential child membranes before using the algorithm
[11] P-Lingua, Main Page [online]. Online available at http://
and only some of them are selected by the algorithm, or
www.p-lingua.org/wiki/index.php/Main_Page (Ac-
the parent-child relationship may change, then some rules cessed August 11, 2020)
ain j may lose relevance. This must be taken into account
[12] Păun, Gh.: Computing with membranes. J. Comput. Syst.
when designing evolution rules, or the presented algorithm Sci. 61(1), 108–143 (2000). Turku Center for Computer
can be enriched with the possibility of dynamic adaption Science-TUCS report 208, November 1998.
of this type of evolution rules; of course, if the side effects [13] Păun, Gh.: Computing with membranes – A Variant: P Sys-
of this modification will be acceptable. tems with Polarized Membranes. Intern. J. of Foundations of
Computer Science, vol. 11, issue 1 (2000), pp. 167–182.
The work is supported by The Ministry of Educa-
[14] Păun, Gh.: Membrane Computing: An Introduction.
tion, Youth and Sports of the Czech Republic from the
Springer, Heidelberg (2002).
National Programme of Sustainability (NPU II) project
[15] Păun, Gh., Rozenberg, G.: A Guide to Membrane Com-
IT4Innovations excellence in science – LQ1602.
puting. Theor. Comp. Science, vol. 287, issue 1, pp. 73–100
(2002).
References [16] Păun, Gh., Rozenberg, A., Salomaa, A. (eds.): The Ox-
ford Handbook of Membrane Computing. Oxford University
[1] Applications of Minimum Spanning Tree Press, New York (2010).
Problem [online]. Geeks for Geeks (2018).
[17] US Patent “Using Spanning Tree Protocol (STP) to En-
URL: https://www.geeksforgeeks.org/
hance Layer-2 Network Topology Maps”, patent number US
applications-of-minimum-spanning-tree/ (Ac-
8,045,488 B2, 2011. Also available at https://patents.
cessed August 14, 2020)
google.com/patent/US8045488B2/en. (Accessed June
[2] 802.1D-2004 – IEEE Standard for Local and metropolitan 4, 2020)
area networks: Media Access Control (MAC) Bridges [on-
[18] The P Systems Website: http://psystems.eu (Accessed
line]. IEEE (2011). URL: https://ieeexplore.ieee.
June 4, 2020)
org/document/1309630 (Accessed June 4, 2020)
[3] Bazlamaçcı, C.F., Hindi, K.S.: Minimum-weight span-
ning tree algorithms: A survey and empirical study.
Computers & Operations Researche, vol. 28, issue 8,
ISSN 0305-0548, pp. 767–785 (2001), online avail-
able at: http://www.sciencedirect.com/science/
article/pii/S0305054800000071
[4] Calude, C., Păun, Gh.: Computing with Cells and Atoms.
Taylor and Francis, London, 2000 (Chapter 3: “Computing
with Membranes”).
[5] ComputerNetworkingNotes: STP – Spanning Tree Pro-
tocol Explained With Examples [online]. Networking
Tutorials (2020). Online available at https://www.
computernetworkingnotes.com/ccna-study-guide/
stp-spanning-tree-protocol-explained-with-examples.
html (Accessed June 4, 2020)
[6] Curtis, S.A.: The classification of greedy algorithms. El-
sevier, 2003. Also available at https://core.ac.uk/
download/pdf/82042073.pdf (Accessed June 4, 2020)