In this paper, the authors propose a new approach to fully asynchronous P systems, and a matching complexity measure, both inspired from the field of distributed algorithms. The authors validate the proposed approach by implementing several well-known distributed depth-first search (DFS) and breadth-first search (BFS) algorithms. Empirical results show that the proposed P algorithms have shorter descriptions and achieve a performance comparable to the corresponding distributed algorithms.
Top1. Introduction
A P system is a computational model inspired by the structure and interactions of cell membranes, introduced by Păun (1998) and Păun, Rozenberg, and Salomaa (2010). The essential specification of a P system includes a membrane structure, objects and rules. Cells evolve by applying rules in a non-deterministic and (potentially maximally) parallel manner. These characteristics make P systems a promising candidate as a model for distributed and parallel computing.
The traditional P system model is synchronous, i.e., all cells evolution is controlled by a single global clock. P systems with various asynchronous features have been investigated by recent research (Frisco, 2004; Casiraghi, Ferretti, Gallini, & Mauri, 2005; Cavaliere & Sburlan, 2004; Cavaliere et al., 2008; Cavaliere & Mura, 2008; Cavaliere et al., 2009; Freund, 2005; Gutiérrez-Naranjo & Pérez-Jiménez, 2010; Kleijn & Koutny, 2006; Pan, Zeng, & Zhang, 2011; Yuan & Zhang, 2007). Here we are looking for similar but simpler definitions, closer to the definitions used in distributed algorithms (Lynch, 1996; Tel, 2000), which should in the future enable us to consider essential distributed features, such as fairness, safety, liveness and infinite evolutions. In our approach, algorithms are non-deterministic, not necessarily constrained to return exactly the same result.
Fully asynchronous P systems are characterized by the absence of any system clock, let alone a global one; however, an outside observer may very well use a clock to time the evolutions. Our approach, based on classical notions in distributed algorithms, as presented by Tel (2000), does not require any change in the static description of P systems, only their evolutions differ (i.e., the underlying runtime engine works differently): (1) for each cell, each step starts after a random delay t (after the preceding step); (2) for each cell, each step, once started, takes zero time (i.e., it occurs instantaneously); (3) for each message, its transmission delay t is random (from its origin until it arrives at its target).
A full version of this paper appears as a CDMTCS report (Nicolescu & Wu, 2011b).
Top2. Preliminaries
We assume that the reader is familiar with the basic terminology and notations, such as alphabets, strings, multisets, relations, graphs, nodes (vertices), edges, directed graphs (digraphs), directed acyclic graphs (dags), arcs, depth-first search (DFS), breadth-first search (BFS), spanning tree, DFS and BFS spanning trees.
In this paper, we use a simple P module—an umbrella concept, which is general enough to cover several basic synchronous P system families, with states, priorities, promoters and duplex channels. In this basic model, the cells evolve synchronously. For the full definition of P modules and modular compositions, we refer readers to Dinneen, Kim, and Nicolescu (2010c). Essentially, a simple P module is a system, Π = (O,σ1,σ2,…,σn,δ), where:
- 1.
O is a finite non-empty alphabet of elementary objects;
- 2.
σ1,σ2,…,σn are cells, of the form σi = (Qi,Si,0,wi,0,Ri), 1 ≤ i ≤ n, where:
- a.
Qi is a finite set of states;
- b.
Si,0 ∈ Qi is the initial state;
- c.
wi,0 ∈ O* is the initial multiset of objects;
- d.
Ri is a finite ordered set of rewriting/communication rules of the form:
S x → α S′ x′ (y)β |z, where: S,S′ ∈ Qi, x,x′,y,z ∈ O*, α ∈ {min,max}, β ∈{↑,↓,↕}.
- 3.
δ is a set of digraph (head,tail) arcs on {1, 2,…,n}, without reflexive arcs, representing duplex channels between cells.