Abstract
The study of networks with small error probability was inaugurated by J.v. Neumann in [1] in 1952. Assume there is a complete set of (unreliable) gates with error probability ɛ smaller than 1/2. One of the central results in this field (argued heuristically by von Neumann and proved rigorously by R.L. Dobrushin and S.I. Ortyukov [5] in 1977) is the following: Let γ be any (extremely small) positive constant. Further let A be a network realizing Boolean function f provided no gate has failed. (The error probability of A may be very great.) Let C(A) be the complexity of A (i.e. the sum of "costs" of its elements). Then the function f can be realized by a (reliable) network à with error probability not greater than ɛ+γ and complexity O(C(A)logC(A)). N. Pippanger [2] showed in 1985 that for almost all Boolean functions f there are networks à with complexity O(C(A)) instead of O(C(A)logC(A)). The proof is very easy and ingenious. Note that O(C(A)) means the following: There is a constant c1 such that C(Ã)≤c1C(A). Constant c1 was not determined by Pippenger, but it seems to be very great. We show that there is a constant c2=c2(ɛ) such that C(Ã)≤c2C(A), where c2(ɛ) → 1 if ɛ → 0. Thus, for almost all Boolean functions networks constructed by our method have very small error probabilities (near that of the elements) and almost minimal complexity.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Neumann von, J.: Probabilistic Logic of Reliable Organism from Unreliable Components. In: C. E. Shannon and J. Mc Carthy (Eds.), Automata studies, Princeton University Press (1956) 43–98.
Pippenger, N.: On Networks of Noisy Gates. 26. Symposium on Foundation on Computer science, 21.–23.10.1985, Portland, 30–38.
Lupanov, O.B.: On a Method of Synthesis of Networks. Izv. Vysš. Učebn. Zaved. Radiofizike 1 (1958) 1, 120–140. (Russian)
Savage, J.E.: The Complexity of Computing. Wiley-Interscience, New York, 1976.
Dobrushin, R.L. and S.I. Ortyukov: Upper Bound for Redundancy of Self-Correcting Arrangements of Unreliable Functional Elements. Prob of Info Transm. 13 (1977), 203–218.
Dobrushin, R.L. and S.I. Ortyukov: On the Lower Bound for Redundancy of Self-Correcting Networks of Unreliable Functional Elements. Prob. Peredači Informacii 13 (1977) 1, 82–89 (Russ.)
Ortyukov, S.I.: On the Synthesis of Asymptotically Non-redundant Self-Correcting Networks of Unreliable Functional Elements. Prob. Peredači Informacii 13 (1977) 4, 3–8. (Russ.)
Kirienko, G.I.: Synthesis of Combinatorial Networks which are Self-Correcting Referring to a Growing Number of Errors. Diskrenij analiz, Sb. Trudov IM SI AN SSSR 16 (1970) 38–43. (Russian)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1987 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Uhlig, D. (1987). On reliable networks from unreliable gates. In: Albrecht, A., Jung, H., Mehlhorn, K. (eds) Parallel Algorithms and Architectures. Lecture Notes in Computer Science, vol 269. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-18099-0_41
Download citation
DOI: https://doi.org/10.1007/3-540-18099-0_41
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18099-9
Online ISBN: 978-3-540-47760-0
eBook Packages: Springer Book Archive