| Autor: |
Yvo Desmedt, Mike Burmester, Yongge Wang |
| Rok vydání: |
2000 |
| Předmět: |
|
| Zdroj: |
Fundamenta Informaticae. 42:61-73 |
| ISSN: |
0169-2968 |
| Popis: |
We consider the problem of dependable computation with multiple inputs. The goal is to study when redundancy can help to achieve survivability and when it cannot. We use AND/OR graphs to model fault tolerant computations with multiple inputs. While there is a polynomial time algorithm for finding vertex disjoint paths in networks, we will show that the equivalent problem in computation systems with multiple inputs is NP-hard. Our main results are as follows. (1) We present a general model for fault tolerant computation systems with multiple inputs: AND/OR graphs. (2) We show that it is NP-hard to find two vertex disjoint solution graphs in an AND/OR graph. It follows that in the general case redundancy cannot help to achieve survivability, assuming P≠NP. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
