Search Results

Approximate Byzantine Agreement (ABA) protocols enable nonfaulty replicas with different initial values to derive a values within a ε-neighborhood of each other, despite the presence of Byzantine behavior. While they give strong guarantees for this ε-agreement property, they tend to have weaker guarantees that the derived value is accurate with respect to some ground truth. Worse, they often have impractical requirements such as large replica sets proportional to data dimensionality, or a priori knowledge of the maximum distance between nonfaulty values. In Stochastic Byzantine Agreement (SBA), the distribution of the nonfaulty values is the result of a stochastic process influenced by sensor measurement error or other sources of noise that affect system outputs. For these scenarios, we present Proximal Byzantine Agreement (PBA), a stochastic Byzantine agreement protocol which infers the most likely output of replicated computation based on the proposed values observed by each replica. Unlike ABA protocols, PBA prioritizes accuracy over agreement. PBA accuracy is relative to the variance of nonfaulty values, yielding comparatively more accurate results for noisy data, particularly when noise is asymmetric. Our evaluations demonstrate this accuracy scales with data dimensionality, outperforming or only mildly underperforming methods that require quorums with up to 10× more replicas and 4× to 124× more computation time per agreement decision, even at relatively low dimensions (d = 4 to d = 18).