Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2000

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!
Sesja wygasła!

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: dependable computation

Sortuj według:

Ogranicz wyniki do:

Models for dependable computation with multiple inputs and some hardness results

Wang Y., Desmedt Y., Burmester M.

Fundamenta Informaticae

2000

Vol. 42, Nr 1

61-73

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. We present a general model for fault tolerant computation systems with multiple inputs: AND/OR graphs. 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.