• Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 5 Apr 2025 (v1), last revised 19 Feb 2026 (this version, v2)] Title:Obfuscated Consensus View PDF HTML (experimental)Abstract:The classic Fischer, Lynch, and Paterson impossibility proof demonstrates that any deterministic protocol for consensus in either a message-passing or shared-memory system must violate at least one of termination, validity, or agreement in some execution. • But it does not provide an efficient procedure to find such a bad execution. • We show that for wait-free shared memory consensus, given a protocol in which each process performs at most $s$ steps computed with total time complexity at most t, there exists an adversary algorithm that takes the process’s programs as input and computes within $O(st)$ time a schedule that violates agreement. • We argue that this bound is tight assuming the random oracle hypothesis: there exists a deterministic obfuscated consensus protocol that forces the adversary to spend $\Omega(st)$ time to find a bad execution despite having full access to all information available to the protocol. • This bound is based on a general algorithm that reduces the constructing an obfuscated consensus protocol to constructing an obfuscated threshold function that provably costs $\Omega(t)$ time to evaluate on a single input, where $t$ is a tunable parameter, and for which an adversary with access to the threshold function implementation cannot extract the threshold an

Article Summaries:

  • Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 5 Apr 2025 (v1), last revised 19 Feb 2026 (this version, v2)] Title:Obfuscated Consensus View PDF HTML (experimental)Abstract:The classic Fischer, Lynch, and Paterson impossibility proof demonstrates that any deterministic protocol for consensus in either a message-passing or shared-memory system must violate at least one of termination, validity, or agreement in some execution. But it does not provide an efficient procedure to find such a bad execution. We show that for wait-free shared memory consensus, given a pro

Sources: