TR-IIS-01-001    zipfile

The computation task of a distributed processing system usually can be partitioned into a set of modules and then modeled as a directed graph, called the task digraph. In the task digraph, vertices represent modules and arcs represent message passing links between two modules. Particularly, according to the logical structures and precedence relationships among modules, a large class of task digraphs can be modeled as And-Or Series-Parallel (AOSP) digraphs. For this type of digraph, we can calculate its task reliability and task response time in linear time; whereas these problems are known to be NP-hard for general digraphs. Hence, it becomes a useful work for evaluating comptation tasks to examine if a task digraph is an AOSP digraph.
A polynomial time algorithm of recognizing AOSP digraphs has been proposed in [1] earlier. In this paper, we consider the fault-tolerant variants of AOSP digraphs, named Replicated And-Or Series-Parallel (RAOSP) digraphs, which are obtained from AOSP digraphs by adding replications to each vertex and adding proper arcs between two vertices. For RAOSP digraphs, we can also calculate its task reliability and task response time in linear time with the similar methods of AOSP digraphs. So it is another important work to recognize RAOSP digraphs. The existing polynomial time recognition algorithm for AOSP digraphs does not apply here since it can be shown that RAOSP digraphs are not AOSP digraphs. To make up this deficiency, we will propose a polynomial time algorithm for recognizing RAOSP digraphs in the context. Moreover, it will be first described how to recognize a special subclass of RAOSP digraphs, Replicated Edge Series-Parallel (RESP) digraphs, in polynomial time as a preliminary step.

Keywords: Task digraphs, AOSP digraphs, graph recognition, fault tolerance, distributed processing systems.