Abstract:
A P system is a parallel and distributed computational model inspired by the structure and interactions of living cells [55]. Chapter 1 first relates mainstream concepts of distributed computing to distributed features proposed for P systems. Chapter 2 introduces xP systems, which are extended versions of simple P systems proposed in our joint work [51, 3, 52, 22, 50]. This thesis investigates the adequacy of xP systems for modelling fundamental synchronous and asynchronous distributed algorithms and aims to construct xP specifications, i.e. directly executable formal specifications of algorithms in xP systems, which: (1) achieve the same runtime complexities as corresponding distributed algorithms and (2) are comparable in program size with high-level pseudocodes of corresponding distributed algorithms. Chapter 3 presents xP specifications of several fundamental traversal algorithms: Echo, distributed depth-first search (DFS), distributed breadth-first search (BFS) and neighbour discovery algorithms, based on our joint work [3]. As new contributions in this thesis, we address the common problem in distributed algorithms, termination detection problem, and provide xP specifications of several well-known termination detection algorithms and their applications. Chapter 4 discusses a series of distributed synchronous DFS and BFS-based edge- and node-disjoint paths algorithms. Consider a digraph with n nodes and m arcs, where f is the maximum number of disjoint paths and d is the outdegree of the source node. Dinneen et al.'s [18] algorithms based on the classical DFS run in O(mf); using Cidon's DFS and Theorem 4.5, our improved algorithms [52] run in O(nf); using a different idea, our two other DFS-based algorithms [22] run in O(nd) and O(nf). The first BFS-based P system solutions in our joint work [51, 52] run in O(nf); an improved version as my own work [65] also runs in O(nf). Following my own work [64], Chapter 5 presents a solution for one of the most challenging distributed computing problems: minimum spanning tree (MST) problem. We discuss the SynchGHS algorithm [42] and our synchronisation barriers. Given a weighted graph with n nodes, our xP solution runs in O(n log n) and it is the first MST solution in P systems.