A Comprehensive Taxonomy of Non-Deterministic Edge Cases in Distributed Consensus Protocols With Specific Attention to Byzantine Fault Tolerance and Partial Network Partition Scenarios

I would like to open a formal discussion on what I consider to be an insufficiently documented area of distributed systems research: the precise taxonomy of failure modes that occur at the intersection of Byzantine fault tolerance mechanisms and partial network partitions, specifically focusing on scenarios where a subset of nodes can communicate with each other but not with the rest of the cluster. The Paxos family (Basic Paxos, Multi-Paxos) handles fail-stop failures through its two-phase structure, while PBFT addresses Byzantine faults up to f = 1/3 of n, and more modern variants like HotStuff optimize for leader changes in partially synchronous models. However, I have identified a series of edge cases where the safety guarantees begin to degrade under specific network conditions that do not strictly qualify as total partition or pure crash-fault. For instance: consider a scenario with 4 nodes (f=1 Byzantine allowed) where node A can talk to B and C but not D; node D is honest but isolated; node B is honest; node C is the Byzantine actor who selectively sends different messages to A and D based on whether it detects their connectivity. The protocol's safety hinges on quorum intersection, but a partially connected graph invalidates the assumption that any two quorums share at least one non-faulty member because the view of 'quorum membership' is inconsistent across nodes due to partition visibility. I would like to propose a formal framework for classifying these hybrid fault models — partial Byzantine (where some nodes are fully honest, some partially adversarial with restricted communication channels, and others completely malicious) — and ask whether current TLA+ specifications or Coq proofs of safety in BFT systems adequately cover the edge cases where network topology is dynamic rather than static. Additionally, I would like to discuss how a leader election protocol handles situations where it elects a node that has been partially partitioned

This is a really interesting paper, but I'd be curious about how these edge cases hold up under practical network conditions versus controlled simulation. The BFT formalism assumes specific adversary behaviors that don't always map to real-world failure modes -- for example, partial partitions are much rarer than the Byzantine model suggests because hardware failures tend to be binary rather than partially deterministic in their misbehavior.