Using approximation hardness to achieve dependable computation.
In: Luby, M and Rolim, J and Serna, M, (eds.)
RANDOMIZATION AND APPROXIMATION TECHNIQUES IN COMPUTER SCIENCE.
(pp. 172 - 186).
Redundancy has been utilized to achieve fault tolerant computation and to achieve reliable communication in networks of processors. These techniques can only be extended to computations solely based on functions in one input in which redundant hardware or software (servers) are used to compute intermediate and end results. However, almost all practical computation systems consist of components which are based on computations with multiple inputs. Wang, Desmedt, and Burmester have used AND/OR graphs to model this scenario. Roughly speaking, an AND/OR graph is a directed graph with two types of vertices, labeled boolean AND-vertices and boolean OR-vertices. In this case, processors which need all their inputs in order to operate could be represented by boolean AND-vertices, whereas processors which can choose one of their "redundant" inputs could be represented by boolean OR-vertices. In this paper, using the results for hardness of approximation and optimization problems, we will design dependable computation systems which could defeat as many malicious faults as possible. Specifically, assuming certain approximation hardness result, we will construct k-connected AND/OR graphs which could defeat a de-active adversary (therefore a de-passive adversary also) where c > 1 is any given constant. This result improves a great deal on the results for the equivalent communication problems.
|Title:||Using approximation hardness to achieve dependable computation|
|Event:||2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 98)|
|Dates:||1998-10-08 - 1998-10-10|
|UCL classification:||UCL > School of BEAMS > Faculty of Engineering Science > Computer Science|
Archive Staff Only