A Phase Transition and Stochastic Domination in Pippenger's Probabilistic Failure Model for Boolean Networks with Unreliable Gates

Maxim RaginskyarXiv 2003 · DOI · arXiv

Abstract

We study Pippenger's model of Boolean networks with unreliable gates. In this model, the conditional probability that a particular gate fails, given the failure status of any subset of gates preceding it in the network, is bounded from above by some $\epsilon$. We show that if we pick a Boolean network with $n$ gates at random according to the Barak-Erdős model of a random acyclic digraph, such that the expected edge density is $c n^{-1}\log n$, and if $\epsilon$ is equal to a certain function of the size of the largest reflexive, transitive closure of a vertex, then Pippenger's model exhibits a phase transition at $c=1$. Namely, with probability $1-o(1)$ as $n\to\infty$, we have the following: for $0 \le c \le 1$, the minimum of the probability that no gate has failed, taken over all probability distributions of gate failures consistent with Pippenger's model, is equal to $o(1)$, whereas for $c > 1$ it is equal to $\exp(-\frac{c}{e(c-1)}) + o(1)$. We also indicate how a more refined analysis of Pippenger's model, e.g., for the purpose of estimating probabilities of monotone events, can be carried out using the machinery of stochastic domination.

Introduction

Since the early days of computing, researchers like John von Neumann have sought to understand how reliable computation can be achieved using unreliable components. While early models often assumed that gate failures were independent, real-world hardware frequently exhibits correlated failures due to environmental factors like thermal fluctuations or power surges.

This paper, published by Maxim Raginsky in 2003, investigates the global reliability of Boolean networks under Nicholas Pippenger’s "$\epsilon$-admissible" model. In this framework, a gate's failure probability is bounded by $\epsilon$, even when conditioned on the failure status of all preceding gates. By applying tools from random graph theory and statistical mechanics, Raginsky identifies a sharp phase transition in the reliability of these networks as their connectivity density changes.

The Model: Random Digraphs and Dependent Failures

To analyze the behavior of large-scale systems, the paper models the network's architecture using the Barak-Erdős model ($G_d(n, p)$). This is a random directed acyclic graph (DAG) where $n$ ordered vertices are connected by edges with a probability $p$. The density of these connections is governed by a parameter $c$, where $p = c n^{-1} \log n$.

Within this topology, the failure of gates is not treated as a simple coin flip. Instead, Pippenger’s model can be viewed as an adversarial scenario: while the "Programmer" designs the network, a "Demon" chooses a failure distribution that satisfies the $\epsilon$ constraint while attempting to maximize the probability of an error. The paper specifically focuses on the Reflexive Transitive Closure (RTC)—the set of all gates reachable from a specific starting gate—as the size of the RTC directly influences the local failure bound $\epsilon$.

Methodology

The research bridges the gap between local gate failures and global network reliability using several sophisticated mathematical frameworks:

  • Lopsided Lovász Local Lemma: This tool from the probabilistic method is used to prove that there is a non-zero probability that a set of "bad events" (gate failures) will not occur, even when those events are dependent.
  • Stochastic Domination: Raginsky employs this to formally compare different failure distributions. He demonstrates that Pippenger’s complex dependent model can be "dominated" by a simpler independent Bernoulli model. This allows for a more refined analysis of monotone events, such as the probability that a majority of gates function correctly.
  • Compactness Proof: The paper provides a rigorous proof for the compactness of the set of $\epsilon$-admissible measures, a technical necessity for the model's validity that was previously assumed.

Key Results: The $c=1$ Phase Transition

The central finding of the paper is the characterization of a phase transition as the number of gates $n$ approaches infinity. The connectivity parameter $c$ acts as a critical threshold:

  1. Subcritical Phase ($c \le 1$): In sparse networks, the minimum probability of failure-free operation is zero. In this regime, the "Demon" can always find a distribution that ensures at least one gate fails with probability $1-o(1)$.
  2. Supercritical Phase ($c > 1$): In denser networks, the probability of zero failures suddenly jumps to a positive constant: $\exp\left(-\frac{c}{e(c-1)} ight)$.

This result demonstrates that once a certain threshold of connectivity is reached, the network gains a form of structural resilience against even adversarial dependent failures.

Implications and Future Directions

Raginsky’s work provides a rigorous mathematical foundation for understanding reliability in the presence of dependencies. By showing that Pippenger’s model can be dominated by independent models, the paper simplifies the analysis of "increasing" events—events that remain true if more gates are fixed to a working status.

However, the paper notes certain limitations. It focuses on the strict standard of "zero failures," whereas practical engineering often only requires "mostly correct" computation. Furthermore, while the Barak-Erdős model provides a useful theoretical benchmark, real-world CPU architectures are highly structured rather than random. Future work may involve applying these statistical mechanics approaches to non-random topologies or constructing partition functions for directed graphs to better understand symmetry-breaking in computational systems.

Reference: Raginsky, M. (2003). A phase transition and stochastic domination in Pippenger’s probabilistic failure model for Boolean networks with unreliable gates. arXiv:math/0311045v2.

Summary updated

Abstract

We study Pippenger's model of Boolean networks with unreliable gates. In this model, the conditional probability that a particular gate fails, given the failure status of any subset of gates preceding it in the network, is bounded from above by some $ε$. We show that if we pick a Boolean network with $n$ gates at random according to the Barak-Erdős model of a random acyclic digraph, such that the expected edge density is $c n^{-1}\log n$, and if $ε$ is equal to a certain function of the size of the largest reflexive, transitive closure of a vertex (with respect to a particular realization of the random digraph), then Pippenger's model exhibits a phase transition at $c=1$. Namely, with probability $1-o(1)$ as $n\to\infty$, we have the following: for $0 \le c \le 1$, the minimum of the probability that no gate has failed, taken over all probability distributions of gate failures consistent with Pippenger's model, is equal to $o(1)$, whereas for $c >1$ it is equal to $\exp(-\frac{c}{e(c-1)}) + o(1)$. We also indicate how a more refined analysis of Pippenger's model, e.g., for the purpose of estimating probabilities of monotone events, can be carried out using the machinery of stochastic domination.
BibTeX
@misc{raginsky2003phase,
  author = {Maxim Raginsky},
  title = {{A Phase Transition and Stochastic Domination in Pippenger's Probabilistic Failure Model for Boolean Networks with Unreliable Gates}},
  year = {2003},
  eprint = {math/0311045},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/math/0311045},
}
Figure