Abstract:
Membrane systems or P systems are distributed and parallel computing models, inspired by the interconnected structure and function of living cells. This thesis investigates the adequacy of synchronous membrane systems for modelling a set of fundamental distributed algorithms. This thesis provides a coherent approach to specify and analyse a certain class of problems related to distributed algorithms. This thesis presents a set of P algorithms (i.e. algorithms that are implemented using membrane systems) that are comparable (i.e. not necessarily better, but not much worse) to the corresponding distributed algorithms, expressed as high-level pseudocodes, with respect to time complexity and program-size complexity. This thesis introduces a new membrane system model. This new model incorporates features that allow for the reduction of inherent non-determinism (such as allowing for a total order priority on rule sets), allowing a better control of the rule execution strategy of the considered distributed algorithms, which are complex and require clear and well defined threads of execution. This thesis proves that this new model is Turing complete and universal. This thesis presents several broadcast- and echo-based P algorithms, as modular building blocks, for building more complex algorithms. These broadcast- and echobased P algorithms have time complexity of e+k and 2e+k, respectively, where e is the eccentricity of a source and k is an integer constant. Next, this thesis presents two solutions to the _ring squad synchronization problem (FSSP). The first FSSP solution synchronizes digraph-structured P systems in 3e+11 steps, where e is the eccentricity of the general. The second FSSP solution synchronizes tree-structured P systems in h+2r +5 steps, where h and r are the height and radius of the tree, respectively. Finally, this thesis presents solutions to two fundamental problems in graph theory: the edge- and node-disjoint paths problems. For a given membrane system with n cells and m links, these solutions find sets of edge- and node-disjoint paths of maximum cardinality in O(mn) steps. These solutions are the first P algorithms for solving the edge- and node-disjoint paths problems in membrane systems.