Distributed Algorithms in Membrane Systems

Show simple item record

dc.contributor.advisor Nicolescu, R en
dc.contributor.advisor Dinneen, M en
dc.contributor.author Kim, Yun-Bum en
dc.date.accessioned 2012-11-14T23:22:47Z en
dc.date.issued 2012 en
dc.identifier.uri http://hdl.handle.net/2292/19660 en
dc.description.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. en
dc.publisher ResearchSpace@Auckland en
dc.relation.ispartof PhD Thesis - University of Auckland en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.rights.uri http://creativecommons.org/licenses/by-nc-sa/3.0/nz/ en
dc.title Distributed Algorithms in Membrane Systems en
dc.type Thesis en
thesis.degree.grantor The University of Auckland en
thesis.degree.level Doctoral en
thesis.degree.name PhD en
dc.rights.holder Copyright: The Author en
pubs.elements-id 363323 en
pubs.org-id Science en
pubs.org-id School of Computer Science en
pubs.record-created-at-source-date 2012-11-15 en
dc.identifier.wikidata Q112890273

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace