Home // ICAS 2012, The Eighth International Conference on Autonomic and Autonomous Systems // View article

Comparison of Bio-Inspired and Graph-Theoretic Algorithms for Design of Fault-Tolerant Networks

Authors:
Matthias Becker
Waraphan Sarasureeporn
Helena Szczerbicka

Keywords: slime mold, Physarum polycephalum, fault tolerant network, (k,t)-spanner

Abstract:
Recently several approaches have been presented that exploit the ability of Physarum polycephalum to connect several food sources via a network of pipes in order to maintain an efficient food distribution inside the organism. These approaches use the mechanisms found in nature in order to solve a technical problem, namely the design of constructing faulttolerant and efficient connection networks. These works comprise experiments with a real slime mold Physarum polycephalum as well as computer simulations based on a tubular model and an agent-based approach. In this work, we study the suitability of those bio-inspired approaches and compare their performance to a graph-theoretic algorithm for construction of fault-tolerant connection networks, the (k; t)-spanner algorithm. The graphtheoretic algorithm is able to construct graphs with a certain degree of fault tolerance as well as meet a given maximal path length between two arbitrary nodes. However the definition of fault tolerance in previous bio-inspired works differs to that used in graph theory. Thus in our contribution we analyze the bio-inspired approaches as well as the graph-theoretic approach for their efficiency of designing optimal fault-tolerant graphs. We demonstrate the usability of the graph-theoretic approach despite relying on a different definition of fault tolerance. We conclude that classical efficient computational algorithms from graph theory can be adapted and applied in the same field as the bio-inspired approaches for the problem of constructing efficient fault tolerant networks. They often provide an easier to use and more direct solution than bio-inspired approaches, that need more parameter tuning before getting satisfactory results.

Pages: 1 to 7

Copyright: Copyright (c) IARIA, 2012

Publication date: March 25, 2012

Published in: conference

ISSN: 2308-3913

ISBN: 978-1-61208-187-8

Location: St. Maarten, The Netherlands Antilles

Dates: from March 25, 2012 to March 30, 2012