Exact Byzantine Consensus on Undirected Graphs under Local Broadcast Model
Muhammad Samir Khan Syed Shalan Naqvi Nitin H. Vaidya

	Observing Black Holes Spin
    Christopher S. Reynolds
 Institute of Astronomy, Cambridge, CB3 OHA
    December 30, 2023
=======================================================================



    
		










This paper considers the Byzantine consensus problem for nodes with binary inputs. The nodes are interconnected by a network represented as an undirected graph, and the system is assumed to be synchronous.
Under the classical point-to-point communication model, it is well-known <cit.> that the following two conditions are both necessary and sufficient to achieve Byzantine consensus among n nodes in the presence of up to f Byzantine faulty nodes: n ≥ 3f+1 and vertex connectivity at least 2f+1. In the classical point-to-point communication model, it is possible 
for a faulty node to equivocate, i.e., transmit conflicting information to different neighbors. Such equivocation is possible because messages sent by a node to one of its neighbors are not overheard by other neighbors.

This paper considers the local broadcast model. In contrast to the point-to-point communication model, in the local broadcast  model, messages sent by
a node
are received identically by all of its neighbors.
Thus, under the local broadcast model, attempts by a node to send conflicting information
can be detected by
its
neighbors. Under this model, we show that the following two conditions are both necessary and sufficient for Byzantine consensus: vertex connectivity at least ⌊ 3f/2 ⌋ + 1 and minimum node degree at least 2f. Observe that the local broadcast model results in a lower requirement for connectivity and the number of nodes n, as compared to the point-to-point communication model.

We extend the above results to a hybrid model that allows some of the Byzantine faulty nodes to equivocate. The hybrid model bridges the gap between the point-to-point and local broadcast models, and helps to precisely characterize the trade-off between equivocation and network requirements.











	

	

§ INTRODUCTION
 
		
This paper considers Byzantine consensus for nodes with binary inputs. The nodes are interconnected by a communication network represented as an undirected graph, and the system is assumed to be synchronous.
Under the classical point-to-point communication model, it is well-known <cit.> that the following two conditions are both necessary and sufficient to achieve Byzantine consensus among n nodes in the presence of up to f Byzantine faulty nodes: n ≥ 3f+1 and vertex connectivity at least 2f+1. In the classical point-to-point communication model, it is possible 
for a faulty node to equivocate <cit.>, i.e., transmit conflicting information to different neighbors. Such equivocation is possible because messages sent by a node to one of its neighbors are not overheard by other neighbors.

In contrast, in the local broadcast model <cit.> considered in this paper, a message sent by any node
is received identically by all of its neighbors in the communication network.
Thus, under the local broadcast model, attempts by a node to equivocate (i.e., send conflicting information to its neighbors) can be detected by
its
neighbors.

This paper obtains tight necessary and sufficient conditions on the underlying communication network to be able to achieve Byzantine consensus under the local broadcast model. As summarized in Section <ref>, although there has been significant work <cit.> that uses either the local broadcast model or other models that restrict equivocation, tight necessary and sufficient conditions for Byzantine consensus under the local broadcast model have not been obtained previously.
In particular, this paper makes the following contributions, some of which have been documented elsewhere <cit.> as well:


	
  * Necessary and sufficient condition:
	In Sections <ref> and <ref>,

    we establish that, under the local broadcast model, to achieve Byzantine consensus, it is necessary and sufficient for
	the communication graph to have vertex connectivity at least 3f/2+1 and minimum degree at least 2f. Observe that the local broadcast model results in a lower connectivity requirement as compared to the (2f+1)-connectivity required under the point-to-point communication model.

	
	
  * Efficient algorithm: We constructively prove the sufficiency of the tight condition stated above by presenting an algorithm that achieves Byzantine consensus. This algorithm,
	however, is not efficient.
	For the case when vertex connectivity is at least 2f, we have
	a more efficient algorithm, which is presented in the appendices.

	In Section <ref>, we present a tool used in the algorithm which exploits the 2f-connectivity.
	Note that
	for f=1,2, the tight condition presented above implies vertex connectivity of 2 and 4, respectively (i.e., connectivity equal to 2f when f=1,2).
	
	
  * Hybrid model:
	In Section <ref>, we extend the above necessary and sufficient condition to a hybrid model wherein at most t ≤ f faulty nodes may have the ability to equivocate to their neighbors (i.e., the ability to send messages to each neighbor
	without being overheard by the other neighbors), while the remaining faulty nodes are restricted to local broadcast (i.e., their messages will
	be received identically by all the neighbors).
	The point-to-point communication model and the local broadcast
	model are both obtained as special cases of the hybrid model
	when t = f and t = 0, respectively.
	Thus, the hybrid model provides a bridge between those two models and helps to precisely characterize the trade-off between equivocation and network requirements.
	
	
	




























	

§ RELATED WORK
 
		




There is a large body of work on Byzantine fault-tolerant algorithms <cit.>.

Here we focus primarily on related work that imposes constraints on a faulty node's ability to equivocate.








Rabin and Ben-Or <cit.> considered a global broadcast model and showed that n ≥ 2f+1 is both sufficient and necessary for consensus in a synchronous system.
The local broadcast model considered in our work reduces to the global broadcast model	when the network is a complete graph.
The necessary and sufficient conditions obtained in this paper are (not surprisingly) equivalent to n≥ 2f+1 when the network is a complete graph.
Clement et. al. <cit.> also considered non-equivocation in a complete graph under asynchronous communication.
Our work obtains results for arbitrary incomplete graphs with synchronous communication.
	
The goal of a Byzantine broadcast algorithm is to allow a single source node to deliver its message reliably to all the other nodes. Prior work has explored such algorithms under the local broadcast model 
<cit.>.

However, the results for Byzantine broadcast do not provide insights into the network requirements for Byzantine consensus problem considered in this paper.


	
There has been significant work on other similar models, sometimes called “partial broadcast”.
To motivate these models, consider
	a network consisting of several Ethernet channels, with a subset of nodes S_i being connected to channel i. Then, transmission by any node in S_i on channel i will be received by all the nodes in channel i. Each node may be connected to several different such channels. 
	
	
	
	An Ethernet channel  to which h nodes are connected may be viewed as a h-hyperedge in a communication network represented by a hypergraph.
	Fitzi and Maurer <cit.> considered a network in which every subset of three nodes form a hyperedge, in addition to every subset of two nodes also forming a hyperedge (i.e., a complete (2,3)-uniform hypergraph).
	
	Ravikant et. al. <cit.> also considered a (2,3)-uniform hypergraph, but with only a subset of 3-hyperedges being present.
	
	Jaffe et. al. <cit.> gave asymptotically tight bounds for the number of 3-hyperedges required
	in such graphs.
	Amitanand et. al. <cit.> considered a complete network wherein, for each faulty node k, the remaining nodes are partitioned such that transmission by the faulty node k to any node is received identically by all the nodes in its partition.
	One key difference from our work is that we consider incomplete networks, whereas <cit.> assumes that each node can communicate directly with all the other nodes.
	Amitanand et. al. <cit.> considered an adversary structure that characterizes the set of nodes that may be simultaneously faulty, instead of using a threshold on the number of faults.




	Other work <cit.> has explored the trade-off between reliability and privacy on partial broadcast networks.



    Some prior work has explored a restricted class of iterative algorithms that achieve approximate Byzantine consensus under the local broadcast model <cit.>.
    
    In particular, this class of algorithms is iterative in nature,
    with a state variable at each node being updated in each iteration as a linear interpolation of the states of selected neighbors. Due to the restriction on the algorithm behavior, the network requirements exceed the necessary and sufficient conditions
    shown in this paper.
    Additionally, these restricted algorithm structures yield only approximate consensus in finite time.
	Li et. al. <cit.> extended this line of work
	to a network consisting of 3-hyperedges and 2-hyperedges.
	Vaidya et. al. <cit.> have investigated the iterative algorithm structure in the point-to-point communication model.
	
	
	
	
	































































	

§ SYSTEM MODEL AND NOTATION
 
		
We consider a synchronous system. The communication network interconnecting n nodes is represented by an undirected graph G = (V, E). Every node in the system knows graph G. Each node u is represented by vertex u∈ V. We will use the terms node and vertex interchangeably.
Two nodes u and v are neighbors if and only if uv ∈ E is an edge of G.


For a set S⊆ V, node u is said to be a neighbor of set S if u∉S and there exists v∈ S such that uv∈ E.








Each edge uv represents a FIFO link between the two nodes u and v.
When a message m sent by node u is received by node v, node v knows that m was sent by node u.

In Sections <ref> and <ref>, we assume the local broadcast model wherein a message sent by a node u is received identically and correctly by each node v such that uv∈ E (i.e., by each neighbor of u).
A hybrid model is considered later in Section <ref>.






A Byzantine faulty node may exhibit arbitrary behavior.
We consider the Byzantine consensus problem assuming
that each node has a binary input. The goal is for each node to output a binary value, satisfying the following conditions, in the presence of at most f < n Byzantine faulty nodes.


	
  * Agreement:
	All non-faulty nodes must output the same value.
	
  * Validity:
	The output of each non-faulty node must be the input of some non-faulty node.
	
  * Termination:
	All non-faulty nodes must decide on their output in finite time.



    
  Paths in graph G:
    A path is a sequence of nodes such that any two adjacent nodes
    in the sequence are neighbors in the graph.
    
        
  •
        For u,v∈ V, a uv-path P_uv is a path between nodes u and v.
        u and v are endpoints of path P_uv.
        Any node in path P_uv that is not an endpoint
        is said to be an internal node of P_uv.
        All uv-paths have u and v as endpoints, by definition.
        Two uv-paths are node-disjoint if they do not have any  internal nodes in common.
        
        
  •
        For U ⊂ V and a node v ∉U, a Uv-path is a uv-path for some node u ∈ U. All Uv-paths have v as one endpoint.
        Two Uv-paths are node-disjoint if they do not have any nodes in common except endpoint v. In particular, although two node-disjoint Uv-paths have endpoint v in common, the other endpoints are distinct for the two paths.
    
    
    
  Fault-free paths:
    A path is said to exclude a set of nodes X⊂ V if no internal node of the path belongs to X; however, its endpoints may potentially belong to X.
    A path is said to be fault-free if none of its internal nodes are faulty. In other words, a path is fault-free
    if it excludes the set of faulty nodes. Note that a fault-free path may have a faulty node as an endpoint.
    
    
  Degree and Connectivity:
    The degree of a node u is the number of u's neighbors (i.e., the number of edges incident to u).
    Minimum degree of G is the minimum over the degree of all the vertices in G.
    A graph G is k-connected if n > k and removal of less than
    k nodes does not disconnect G.
    By Menger's Theorem <cit.> a graph G is k-connected if and only if for any two nodes u, v ∈ V there exist k node disjoint uv-paths.
    Another standard result <cit.> for k-connected graphs is that if G is k-connected, then for any node v and a set of at least k nodes U there exist k node-disjoint Uv-paths.


	

§ NECESSARY CONDITIONS UNDER LOCAL BROADCAST
 
		

Theorem <ref> below states the
necessary conditions for Byzantine consensus under the local
broadcast model.
Section <ref> presents a Byzantine consensus algorithm and constructively proves that the necessary conditions are also sufficient.



 
	If there exists a Byzantine consensus algorithm under the local broadcast model on graph G tolerating at most f Byzantine faulty nodes, then both the following conditions must be true:
	[label=(*)]
	    
  * G has minimum degree at least 2f, and 
	    
  * G is (3f/2 + 1)-connected.
	


Appendix <ref> presents a  proof of Theorem <ref>.
Necessity of conditions (i) and (ii) in the theorem is proved separately in Lemmas <ref> and <ref>, respectively.
We use a state machine based approach <cit.>
to prove Lemmas <ref> and <ref>.












It should be easy to see that a complete graph consisting of 2f+1 nodes satisfies the necessary conditions in Theorem <ref> for any f.
Figure <ref> presents other examples of graphs that satisfy the necessary conditions. Figure <ref>(a) shows a cycle consisting of 5 nodes. For this graph, the minimum degree is 2, and the graph is 2-connected. Thus, the cycle satisfies the conditions in Theorem <ref> for f=1.

The graph in Figure <ref>(b) satisfies the necessary conditions when f=2.




Section <ref> below proves that the above necessary conditions are also sufficient. Before proceeding to Section <ref>, let us consider the 5-node cycle in Figure <ref>(a) to build some intuition on why these conditions may be sufficient.
Since f=1, we do not have 2f+1 node-disjoint paths between every pair of nodes in the cycle in Figure <ref>(a).


Despite lower connectivity, we can show a useful property.
In particular, suppose that node 1 attempts to send a message M to node 4, by transmitting it along two node-disjoint paths 1-2-3-4 and 1-5-4, respectively.
That is, node 1 will send the message to nodes 2 and 5 (its neighbors) in a single transmission – local broadcast model allows node 1 to send its message to all its neighbors simultaneously.
The neighbors 2 and 5 will then forward the message

and subsequently, node 3
will forward the message received from node 2.

Due to the local broadcast model, all neighbors of each node will receive its transmissions. Consider two cases:



    
  * Case (i):
    The internal nodes (namely, 2, 3 and 5) on the two paths behave correctly: In this case, node 4 receives identical copies of the message along the two disjoint paths.
    Because f=1, node 4 can be certain that it has correctly received the message that was transmitted by node 1 (when  f=1, internal nodes on at most one disjoint path may be faulty).
    
    
  * Case (ii):
    Node 3 is faulty, and tampers the message received from node 2 before forwarding it to node 4: In this case, node 4 will not receive two identical message copies along the two disjoint paths. Therefore, node 4 cannot determine the message sent by node 1. However, in this case, node 2 is non-faulty.
    Node 2 correctly forwards message M received from node 1 to node 3, and then observes that node 3 is forwarding a tampered message to node 4, not the correct message M. Node 2 can observe the faulty behavior of node 3 due to the local broadcast property – when node 3 sends the tampered message to node 4, node 2 receives it too, because node 2 is a neighbor of node 3.
    
    Node 2 can now notify node 1 that node 3 is faulty.
    Of course, on receiving this notification, node 1 cannot be certain whether node 3 is indeed faulty, or node 2 is faulty and it is incorrectly accusing node 3 of misbehavior. However, node 1 can be certain that one of nodes 2 and 3 must be faulty. Because f=1, node 1 can then infer that the path 4-5-1 is fault-free. Thus, any messages received by node 1 from node 4 along the path 4-5-1 could not be tampered by the internal node on this path, namely, node 5. This allows node 1 to now receive messages transmitted by node 4 reliably.



The example above can be generalized to derive a similar capability for reliable communication in at least one direction between each pair of nodes. Although the algorithm presented next does not seem to explicitly utilize this property, it implicitly relies on such a behavior.










	

§ BYZANTINE CONSENSUS ALGORITHM UNDER LOCAL BROADCAST
 
		

Theorem <ref> below states that the necessary conditions in Theorem <ref> are also sufficient.


 
	Under the local broadcast model, Byzantine consensus tolerating at most f Byzantine faulty nodes is achievable on graph G if both the following conditions are true:
	[label=(*)]
	    
  * G has minimum degree at least 2f, and 
	    
  * G is (3f/2 + 1)-connected.
	





We prove correctness of Theorem <ref> constructively by providing a Byzantine consensus algorithm (in Section <ref>) and showing its correctness (in Section <ref>).


	
		

 §.§ Proposed Algorithm
 
			

Assume that graph G satisfies the properties stated
in Theorem <ref>. That is, G has minimum degree at least 2f and is ( 3f / 2  + 1)-connected.

Pseudo-code for the proposed algorithm is presented below.
To understand the description presented next, it will help the reader to read the corresponding steps in Algorithm <ref> below.


    
  Initialization: Each node v∈ V maintains a local state variable named γ_v, which is initialized  to equal node v's binary input.
    
    
  Phases of the algorithm: Recall that we assume a synchronous system. The execution of the algorithm is divided into many phases, each phase corresponding to a distinct subset of nodes F, such that F contains at most f nodes. Each iteration of the For loop in Algorithm <ref> corresponds to one phase of the algorithm. The set F chosen in each phase is a candidate for the actual set of faults; however, set F in only one of the phases will exactly equal the actual set of faulty nodes in the given execution.
    This is similar to the Byzantine consensus algorithm for directed graphs under the point-to-point communication model by Tseng and Vaidya <cit.>.
    However, the rest of the algorithm proceeds differently since we consider the local broadcast model.
    
    
  Step (a): At the beginning of each phase, each node v attempts to communicate its current value of γ_v via “flooding”, as described soon.
    Any message transmitted during flooding has the form (b, Π), where b ∈ 0, 1 and Π is a path.
    Flooding proceeds in synchronous rounds, with each node possibly forwarding messages received in the previous round, following the rules presented below.
    Flooding will end after n rounds, as should be clear from the following description.
    
    To initiate flooding of its γ_v value, node v transmits message (γ_v,) to its neighbors, where  represents an empty path.
    Each node in the network similarly initiates flooding of its own γ value in step (a).
    If v is faulty and does not initiate flooding, then non-faulty neighbors of v replace the missing message with the default message of (1,).
    Therefore, we can assume that a value is indeed flooded by each node, even if it is faulty.
    When node v receives from a neighbor u a message (b,Π), where b∈{0,1} and Π is a path, it takes the following steps sequentially. In the following note that Π-  u denotes a path obtained by concatenating identifier u to path Π.
    
        
  * If path Π- u does not exist in graph G, then node v discards the message (b,Π). Recall that each node knows graph G, and the message (b,Π) was received by node v from node u.
        
  * Else if, in the current phase, node v has previously received from u another message containing path Π (i.e., a message of the form (b',Π)),
        then node v discards the message (b,Π).
        
  * Else if path Π already includes node v's identifier, node v discards the message (b,Π).
        
  * Else node v is said to have received value b along path Π- u and node v forwards message (b,Π- u) to its neighbors. Recall that v received message (b,Π) from neighbor u.
    
    
    Rules (i) and (ii) above are designed to prevent a faulty node from sending spurious messages. Recall that under the local broadcast model, all neighbors of any node receive all its transmissions.
    Thus, rule (ii) above essentially prevents a faulty node from successfully delivering mismatching messages to its neighbors (i.e., this prevents equivocation).
    Rule (iii) ensures that flooding will terminate after n rounds.
    
    Rule (ii) above crucially also ensures the following useful property due to the local broadcast model: even if node u is Byzantine faulty, but paths P_uv and P_uw are fault-free, then nodes v and w will receive
    identical value in the message from u forwarded along paths P_uv and P_uw, respectively.
    Recall that a path is fault-free if none of the internal nodes on the path are faulty.
    
    
  Step (b): Recall that a path is said to exclude set F if none of its internal nodes are in F. For each u∈ V, node v chooses an arbitrary uv-path P_uv
    that excludes F.
    It can be shown (Lemma <ref>) that such a path always exists under the conditions in Theorem <ref>.
    For the purpose of step (b), node v is deemed to have received its own γ_v along
    path P_vv (containing only node v).
    Node v computes sets Z_v and N_v = V - Z_v, as shown in the pseudo-code.
    
    
  Step (c):
    This step specifies the rules for updating value γ_v.
    γ_v is not necessarily updated in each phase.
    
    
  Output:
    After all the phases (i.e., all iterations of the For loop) are completed,
    the value of γ_v is chosen as the output of node v.


The proof of correctness of Algorithm <ref> is presented in Section <ref>. 



As we discussed earlier when describing the flooding mechanism, the faulty nodes are effectively limited to delivering a unique value on all fault-free paths (i.e., paths that do not have faulty nodes as internal nodes). If this unique value corresponding to a faulty node is 0, we will say that the faulty node flooded value 0; else we will say that the node flooded value 1.

Let Z be the set of nodes that flooded 0 in step (a) and let N = V - Z be the set of the remaining nodes that flooded 1.
Recall from the description of flooding above, that even a faulty node effectively floods one value, and one value only, in step (a) of each phase.


Note that either Z or N may possibly be empty, but not both.
In step (b), each non-faulty node v obtains its own estimates Z_v and N_v of Z and V, respectively. If the set F in the current phase does not contain all the faulty nodes, then these estimates can be incorrect.
However, at least in one phase, F will contain all the faulty nodes and, in that phase, as shown later, it is guaranteed that
Z=Z_v and N=N_v.
This observation is important for the correctness of the algorithm, as seen later.






As shown later, step (c) is designed to ensure that the fault-free nodes will reach consensus in a phase in which F contains all the faulty nodes.
In each phase, step (c) also ensures the invariant that γ_v,
at any non-faulty node v, at the end of the phase is equal to γ_u, for some non-faulty node u, at the start of that phase.








			
		

 §.§ Proof of Correctness of Algorithm <ref>
 
			

In this section, we assume that graph G satisfies the conditions stated in Theorem <ref>, even if this is not always stated explicitly below.

Appendix <ref> presents the proofs of the lemmas in this section.




The proof of correctness relies on two key lemmas, Lemma <ref> and <ref>. We will present additional results and discuss the intuition behind the proof of these lemmas subsequently. Formal proofs are presented in Appendix <ref>.
Recall that the algorithm execution is divided into phases, each phase corresponding to a different choice of F, where
|F|≤ f. For convenience of presentation, we will refer to γ_v as the “state of node v”. Recall that state γ_v of node v may possibly be modified in step (c) in each phase.
 
 	For a non-faulty node v, its state γ_v at the end of any given phase equals the state of some non-faulty node at the start of that phase.



 
	Consider a phase of Algorithm <ref> wherein all the faulty nodes are contained in set F corresponding to that phase. At the end of this phase,
	 every pair of non-faulty nodes u, v ∈ V have identical state, i.e., γ_u=γ_v.


As shown next,

these
two lemmas imply correctness of

Algorithm <ref>,
thus proving

Theorem <ref>.

Theorem <ref>

Algorithm <ref> terminates in finite time because the number of phases is finite, and flooding in each phase completes in finite time. Thus, the algorithm satisfies the termination condition.

Since there are at most f faulty nodes in any
given execution, there exists at least one phase in which
set F will contain all the faulty nodes. Then, from Lemma <ref>, we have that all non-faulty nodes have the same state at the end of this phase. Lemma <ref> implies that the state of the non-faulty nodes will remain unchanged after any subsequent phases. Therefore, all non-faulty nodes will have the same state at the end of the algorithm and their output will be identical. This proves that the algorithm satisfies the agreement condition.

At the start of phase 1, the state of each non-faulty node equals its own input. Now, applying Lemma <ref> inductively implies that the state of a non-faulty node always equals the input of some non-faulty node. This, in turn,
implies that the algorithm satisfies the validity condition.
Thus, we have proved correctness of Algorithm <ref> under the conditions stated in Theorem <ref>.






The proofs of Lemmas <ref> and <ref>, stated above, rely on two other lemmas, presented next. The reader may skip the rest of this section without a loss of continuity.







Lemma <ref> below implies that path P_uv used in step (b) of the algorithm indeed exists.

 
	For any choice of set F in the algorithm, and any two nodes u, v∈ V, there exists a uv-path that excludes F.



Recall that a path is said to exclude F if none of the
internal nodes in the path belong to F.




Since G is (3f/2+1)-connected, by Menger's Theorem, there are at least 3f/2+1 node-disjoint paths between any two nodes u, v.
For any f≥ 0, we have
3f/2+1≥ f+1.
Thus, there are at least f+1 node-disjoint uv-paths, of which at least one path must exclude F, since F≤ f.




The next lemma states that the choice of sets A_v and B_v in step (c) ensures that the node-disjoint paths used in that step indeed exist.

 
	For any non-faulty node v, and any given phase with the corresponding set F, in step (c), if v ∈ B_v, then there exist f+1 node-disjoint A_v v-paths that exclude F.


The formal proof of the above lemma is presented in Appendix <ref>. Observe that there are four distinct cases in step (c) for determining sets A_v and B_v. The proof of the above claim in cases 1 and 3 in step (c) follows from (3f/2+1)-connectivity of graph G, while the proof in cases 2 and 4 follows from the fact that the minimum degree
of G is at least 2f.

In step (c), observe that if node v modifies its state γ_v, then
it must have received identical value along f+1
node-disjoint A_v v paths.
So, at least one of these path must not only be fault-free, but also have

non-faulty endpoints.
The proof of Lemma <ref> in Appendix <ref> relies on this observation.

Now consider Lemma <ref>.
The correctness of this lemma relies on the local broadcast property and rule (ii) used in flooding.
Suppose that set F in a certain phase contains all the faulty nodes. Since the paths used in step (b) of the algorithm exclude set F, these paths
are fault-free (i.e., none of their internal nodes are faulty).
Then, the earlier discussion of flooding implies that any two non-faulty nodes u,v will obtain Z_u=Z_v and N_u=N_v in step (b) of this phase. By a similar argument, all the paths used in step (c) of this phase are also fault-free, and any two non-faulty nodes will end step (c) of this phase with an identical state. A complete proof of Lemma <ref> is presented in Appendix <ref>.
			
		

 §.§ An Efficient Algorithm
 
		    
The number of phases in Algorithm <ref> is exponential in f, since there exists one phase corresponding to each choice of set F such that |F|≤ f.
When the communication graph G is 2f-connected, we have developed an efficient algorithm that requires O(n) time.
Although in general 2f-connectivity is a stronger requirement on graph G as compared to the requirement in Theorem <ref>, observe that when f=1,2 these two requirements are equivalent.

 
	Under the local broadcast model, if G is 2f-connected, then Byzantine consensus tolerating at most f Byzantine faults is achievable on graph G in O(n) synchronous rounds.


We prove Theorem <ref> constructively by giving an efficient algorithm, which we present in Appendix <ref>.

Using the example in Figure <ref>(a), we now illustrate a tool used in that algorithm, which exploits the 2f-connectivity.
The graph in Figure <ref>(a) is 2-connected, i.e., 2f-connected for f=1.
Similar to our algorithm in the previous section, suppose that node 1 floods value b, which is propagated to node 4 along path 1-2-3-4.

When node 2 forwards the value to node 3, all of node 2's neighbors hear the forwarded message. Similarly, when node 3 forwards the message to node 4, all of node 3's neighbors hear the forwarded message.

Suppose now that we ask each node to additionally “report” on its neighbors by flooding any messages heard/received in the above propagation from node 1 to node 5. Then the message forwarded by node 4, as overheard by node 3, will be flooded by node 3. Since the graph G is 2f-connected, node 4 has at least 2f neighbors, each of which will take similar steps.  Now consider two cases:

    
  * Node 3 is faulty:
    Since node 3 is faulty, there are at most f-1 other faulty nodes.
    In this case, 2f-connectivity implies that there are at least f+1 node-disjoint fault-free paths from neighbors of node 3 to node 1.
    Thus, node 1 can receive f+1 identical and correct reports of all messages transmitted by node 3.
    Therefore, node 1 can correctly determine the message forwarded by node 3.
    In general, each node can correctly learn messages transmitted by any faulty node, when the connectivity is 2f.
    
    
  * Node 3 is non-faulty:
    In this case, it is possible that node 1 does not receive identical reports about node 3's messages on f+1 node-disjoint paths.
    This inability to receive f+1 identical reports, however, allows node 1 to infer that node 3 must be non-faulty.

In summary, as illustrated above, each node can observe all messages sent by any faulty node. Also, each node can either observe all messages sent by
another

non-faulty node, or learn that it is non-faulty.
In some instances, these observations help non-faulty nodes

identify
the
faulty nodes accurately.
Our algorithm in Appendix <ref> relies on this property to improve the time complexity.
		
	

§ HYBRID MODEL
 
		

In this section we consider a hybrid model. The hybrid model is designed to help explore the gap between the network requirements for Byzantine consensus under the point-to-point communication model and the local broadcast model.

Under the hybrid model, up to f < n nodes may be Byzantine faulty. The faulty nodes are of two types:

  
  * Equivocating faulty nodes: At most t ≤ f of the faulty nodes may equivocate, that is, they are not restricted to perform local broadcast. If u is an equivocating faulty node and has neighbors v and w,
  then node u may send message M_v to node v without node w receiving M_v, and similarly send message M_w to node w without node v receiving M_w. Thus, equivocating faulty nodes can behave similar to the faulty nodes under the point-to-point communication model.
  
  * Non-equivocating faulty nodes: Any faulty node that is not an equivocating faulty node is said to be a non-equivocating faulty node. A non-equivocating faulty node conforms to the local broadcast model. Thus, if node u is a non-equivocating faulty node, and has neighbors v and w,
  then any message M transmitted by node u will be received identically by v and w both.

Observe that when t = 0, the hybrid model reduces to the local broadcast model, since all the faulty nodes are restricted to perform local broadcast. On the other hand, when t = f, the hybrid model reduces to the classical point-to-point communication model because all the faulty nodes can equivocate.
The following theorem extends results from

Sections <ref> and <ref>
to the hybrid model.

 
	Under the hybrid model, Byzantine consensus tolerating at most f Byzantine faulty nodes, of which at most t are equivocating faulty nodes, is achievable on graph G if and only if all the following conditions are true:
	
		
  * G is (3(f-t)/2 + 2t + 1)-connected,
		
  * if t = 0, then G has minimum degree at least 2f, and
		
  * if t > 0, then every set of nodes S, such that 0 < |S| ≤ t, has at least 2f + 1 neighbors.
	


Observe that when t=0, condition (ii) lower bounds the number of neighbor of each vertex.
On the other hand, when t > 0, condition (iii) lower bounds the number of neighbors of each subset of nodes of size at most t.
Recall that neighbors of S are nodes outside of S that have an edge to some node in S.
Theorem <ref> is proved in Appendix <ref>. Consider three cases:

    
  * When t = 0, as noted earlier, the hybrid model reduces to the local broadcast model. In this case, condition (iii) imposes no restrictions, and conditions (i) and (ii) reduce to the graph requirements in Theorems <ref> and  <ref>.
    
  * When t = f, the hybrid model reduces to the point-to-point communication model. In this case, condition (ii) imposes no restrictions, condition (i) requires G to be (2f+1)-connected, and condition (iii) implies n ≥ 3f+1.
    
  * When 0 < t < f, the above theorem provides insights into the trade-off between equivocation and network requirements.

    
The necessity and sufficiency of the conditions in Theorem <ref> is proved using similar techniques as the proofs of Theorems <ref> and <ref>, respectively.
The proof of Theorem <ref> appears in Appendix <ref>.
To prove sufficiency, Algorithm <ref> is modified to obtain an algorithm for the hybrid model – the modified algorithm is presented in Appendix <ref>.

	

§ SUMMARY
 
		
In this work, we investigated Byzantine Consensus under the local broadcast model.
We showed that (3f/2 + 1)-connectivity and  minimum degree at least 2f are together necessary and sufficient conditions to achieve Byzantine consensus in the presence of at most f Byzantine faults under the local broadcast model.



The sufficiency proof is constructive.
However, the algorithm presented requires exponential synchronous rounds.
For a stronger network condition of 2f-connectivity, an efficient algorithm that achieves consensus in linear number of rounds is presented in Appendix <ref>.

We leave finding an efficient algorithm for the tight condition for future work.

We also considered a hybrid model where some faulty nodes may equivocate but other faulty nodes are restricted to local broadcast.
We presented necessary and sufficient conditions for this model, which provide insights into the trade-off between equivocation and network requirements.








	abbrv
	

	

§ PROOFS OF SECTION <REF>
 
		
In the appendices, with a slight abuse of terminology, we allow a partition of a set to have empty parts.
That is, (Z_1, …, Z_k) is a partition of a set Y if ⋃_i=1^k Z_i = Y and Z_i ∩ Z_j = ∅ for all i  j, but some Z_i's can be possibly empty.

A Byzantine Consensus algorithm 𝒜 outlines a procedure 𝒜_u for each node u ∈ V that describes state transitions of u.

In each synchronous round, each node optionally sends messages to its neighbors, receives messages from the neighbors, and then updates its state.
The new state of u depends entirely on u's previous state and the messages received by u from its neighbors.
The state of u determines the messages sent by u.




 
	If there exists a Byzantine consensus algorithm under the local broadcast model on a graph G tolerating at most f Byzantine faulty nodes, then G has minimum degree at least 2f.














	When f = 0, the lemma does not impose any restrictions on G.
	So we assume that f > 0.
	It is easy to show that, when n > 1, each node must have at least one neighbor to be able to achieve consensus.
	So in the rest of the proof we assume that the degree of each node in G is at least 1.
	Suppose for the sake of contradiction that there exists a node z in G of degree less than 2f and there exists an algorithm 𝒜 that solves Byzantine consensus under the local broadcast model on G.
	Then there exists a partition (F^1, F^2) of the neighborhood of z such that F^1 < f and F^2≤ f.
	Let W = V - (F^1 ∪ F^2 ∪z) be the set of remaining nodes.
	Note that some of these sets can be possibly empty.
	However, since n > f > 0 and z has degree at least 1, we select these sets so that F^2 is necessarily non-empty.
	Recall that 𝒜 outlines a procedure 𝒜_u for each node u that describes u's state transitions in each round.
	
	We first create a network 𝒢 to model behavior of nodes in G in three different executions E_1, E_2, and E_3, which we will describe later.
	Figure <ref> depicts 𝒢.
	The network 𝒢 has some directed edges, the behavior of which will be explained later.
	We denote a directed edge from u to v as uv.
	𝒢 consists of two copies of each node in W and a single copy of the remaining nodes.
	We denote the two sets of copies of W as W_0 and W_1.
	For each node u ∈ W, we denote by u_0 and u_1 the two copies of u in W_0 and W_1 respectively.
	For each edge uv ∈ E(G), we create edges in 𝒢 as follows:
	
		
  * If u, v ∈ W, then there are two edges u_0 v_0 and u_1 v_1 in 𝒢.
		These edges are not shown in Figure <ref>.
		
  * If u, v ∈ V - W, then there is a single edge uv in 𝒢.
		Some of these edges are also not shown in Figure <ref>.
		
  * If u ∈ F^1 and v ∈ W, then there are two edges uv_0 and u v_1 in 𝒢.
		In Figure <ref>, these edges are illustrated by a single undirected edge between sets F^1 and W_0, and a single directed edge from F^1 to W_1.
		
  * If u ∈ F^2 and v ∈ W, then there are two edges uv_0 and u v_1 in 𝒢.
		In Figure <ref>, these edges are illustrated by a single directed edge from F^2 to W_1, and a single undirected edge between sets F^2 and W_0.


	
	Note that there are no edges between W_0 and W_1.
	In Figure <ref>, this is emphasized by drawing a cross on a dotted line between W_0 and W_1.
	
	
	
	All message transmissions in 𝒢 are via local broadcast, as follows.
	When a node u in 𝒢 transmits a message, the following nodes receive this message identically: each node with whom u has an undirected edge and each node to whom there is an edge directed away from u.
	Note that a directed edge e = uv behaves differently for u and v.
	All messages sent by u are received by v.
	No message sent by v is received by u.

	
	
	
	Observe that with this behavior of directed edges, the structure of 𝒢 ensures the following property.
	For each edge uv in the original graph G, each copy of u receives messages from exactly one copy of v in 𝒢.
	
	This allows us to create an algorithm for 𝒢 corresponding to 𝒜 as follows.
	For each node u ∈ G, if 𝒢 has one copy of u, then u runs 𝒜_u.
	Otherwise there are two copies u_0 and u_1 of u.
	Both u_0 and u_1 run 𝒜_u.
	
	Consider an execution ℰ of the above algorithm on 𝒢 as follows.
	Each node in W_0 ∪ F^1 ∪z has input 0 and the remaining nodes have input 1.
	
	Observe that it is not guaranteed that nodes in 𝒢 will decide on the same value or that the algorithm will terminate.
	We will show that the algorithm does indeed terminate but nodes do not reach agreement in 𝒢, which will be useful in deriving the desired contradiction.
	We use ℰ to describe three executions E_1, E_2, and E_3 of 𝒜 on the original graph G as follows (see also Table <ref>).
	
		
  * F^2 is the set of faulty nodes.
		In each round, a faulty node broadcasts the same messages as the corresponding node in 𝒢 in execution ℰ in the same round.
		All non-faulty nodes have input 0.
		Note that the behavior of non-faulty nodes in F^1 ∪z and W is modelled by the corresponding (copies of) nodes in F^1 ∪z and W_0, respectively, in ℰ.

        Since 𝒜 solves Byzantine consensus on G, nodes in W ∪ F^1 ∪z decide on output 0 (by validity) in finite time.
		
		
  * F^1 is the set of faulty nodes.
		In each round, a faulty node broadcasts the same messages as the corresponding node in 𝒢 in execution ℰ in the same round.
		z has input 0 and all the remaining non-faulty nodes have input 1.
		Note that the behavior of non-faulty nodes in F^2 ∪z and W is modelled by the corresponding (copies of) nodes in F^2 ∪z and W_1, respectively, in ℰ.

        The output of the non-faulty nodes will be described later.
		
		
  * F^1 ∪z is the set of faulty nodes.
		In each round, a faulty node broadcasts the same messages as the corresponding node in 𝒢 in execution ℰ in the same round.
		All non-faulty nodes have input 1.
		Note that the behavior of non-faulty nodes in F^2 and W is modelled by the corresponding (copies of) nodes in F^2 and W_1, respectively, in ℰ.
        Since 𝒜 solves Byzantine consensus on G, nodes in W ∪ F^2 decide on output 1 (by validity) in finite time.

	
	
	
		
		
		
	
	
	
	
	
	
	
	
	
	Due to the output of nodes in W ∪ F^1 ∪z in E_1, the nodes in W_0 ∪ F^1 ∪z output 0 in ℰ.
	Similarly, due to the output of nodes in W ∪ F^2 in E_3, the nodes in W_1 ∪ F^2 output 1 in ℰ.



	It follows that in E_2, nodes in W and F^2, as modeled by W_1 and F^2 in ℰ, output 1 while z outputs 0.
	Recall that, by construction, F^2 is non-empty.
	This violates agreement, a contradiction.



 
	If there exists a Byzantine consensus algorithm under the local broadcast model on a graph G tolerating at most f Byzantine faulty nodes, then G is (3f/2 + 1)-connected.



	Suppose for the sake of contradiction that G is not (3f/2 + 1)-connected and there exists an algorithm 𝒜 that solves Byzantine consensus under the local broadcast model on G.
	Then there exists a vertex cut C of G of size at most 3f/2 with a partition (A, B, C) of V such that A and B (both non-empty) are disconnected in G - C (so there is no edge between a node in A and a node in B).
	Since C≤3f/2, there exists a partition (C^1, C^2, C^3) of C such that C^1, C^2≤f/2 and C^3≤f/2.
	Recall that 𝒜 outlines a procedure 𝒜_u for each node u that describes u's state transitions in each round.
	
	Similar to the proof of Lemma <ref>, we first create a network 𝒢 to model behavior of nodes in G in three different executions E_1, E_2, and E_3, which we will describe later.
	𝒢 consists of two copies of each node in A and B, and a single copy of the remaining nodes.
	Figure <ref> depicts 𝒢.
	The edges in 𝒢 can be deduced from Figure <ref> along the lines of the proof of Lemma <ref>.
	However, edges within C are not shown in Figure <ref>.
	They are copied exactly from G.

	As in proof of Lemma <ref>, the structure of 𝒢 ensures that, for each edge uv in the original graph G, each copy of u receives messages from exactly one copy of v in 𝒢.
	This allows us to create an algorithm for 𝒢 corresponding to 𝒜 as follows.
	For each node u ∈ G, if 𝒢 has one copy of u then u runs 𝒜_u.
	Otherwise there are two copies u_0 and u_1 of u.
	Both u_0 and u_1 run 𝒜_u.
	
	
	
	Consider an execution ℰ of the above algorithm on 𝒢 as follows.
	Each node in A_0, B_0, and C^1 has input 0 and the remaining nodes have input 1.
	As in proof of Lemma <ref>, we will show that the algorithm does indeed terminate but nodes do not reach agreement in 𝒢, which will be useful in deriving the desired contradiction.
	We use ℰ to describe three executions E_1, E_2, and E_3 of 𝒜 on the original graph G as follows.
	
		
  * C^2 ∪ C^3 is the set of faulty nodes.
		In each round, a faulty node in C^2 ∪ C^3 broadcasts the same messages as the corresponding node in 𝒢 in execution ℰ in the same round.
		All non-faulty nodes have input 0.
		Note that the behavior of non-faulty nodes in A, B, and C^1 is modelled by the corresponding (copies of) nodes in A_0, B_0, and C^1, respectively, in ℰ.

        Since 𝒜 solves Byzantine consensus on G, nodes in A, B, and C^1 decide on output 0 (by validity) in finite time.
		
		
  * C^1 ∪ C^3 is the set of faulty nodes.
		In each round, a faulty node in C^1 ∪ C^3 broadcasts the same messages as the corresponding node in 𝒢 in execution ℰ in the same round.
		A has input 0 and all the remaining non-faulty nodes have input 1.
		Note that the behavior of non-faulty nodes in A, B, and C^2 is modelled by the corresponding (copies of) nodes in A_0, B_1, and C^2, respectively, in ℰ.

        The output of the non-faulty nodes will be described later.
		
		
  * C^1 ∪ C^2 is the set of faulty nodes.
		In each round, a faulty node in C^1 ∪ C^2 broadcasts the same messages as the corresponding node in 𝒢 in execution ℰ in the same round.
		All non-faulty nodes have input 1.
		Note that the behavior of non-faulty nodes in A, B, and C^3 is modelled by the corresponding (copies of) nodes in A_1, B_1, and C^3, respectively, in ℰ.

        Since 𝒜 solves Byzantine consensus on G, nodes in A, B, and C^3 decide on output 1 (by validity) in finite time.
	
	



    Due to the output of nodes in A, B, and C^1 in E_1, the nodes in A_0, B_0, and C^1 output 0 in ℰ.
    Similarly, due to the output of nodes in A, B, and C^3 in E_3, the nodes in A_1, B_1, and C^3 output 1 in ℰ.
	It follows that in E_2, nodes in A, as modeled by A_0 in ℰ, output 0 while nodes in B, as modeled by B_1, output 1.
	Recall that, by construction, both A and B are non-empty.
	This violates agreement, a contradiction.


 

Theorem <ref>
	Directly from Lemmas <ref> and <ref>.

	
	

§ PROOFS OF SECTION <REF>
 
		
In this section, we assume that the graph G satisfies the conditions in Theorem <ref>.
The following observation follows from the rules used for flooding.

 
	For any phase of Algorithm <ref>, in step (a) for any two nodes u, v ∈ V (possibly faulty), if v receives value b along a fault-free uv-path then u broadcast the value b to its neighbors during flooding.


Recall that, if a faulty node does not initiate flooding, then for the purpose of the above observation, its behavior is equivalent to it flooding the value 1.
We now give proofs of Lemmas <ref>, <ref>, and <ref>.

Lemma <ref>
	Fix a phase of the algorithm and the corresponding set F.
	Consider an arbitrary non-faulty node v such that v ∈ B_v in step (c).
	There are 4 cases to consider, corresponding to the 4 cases in step (c).
	
		
  * Z_v ∩ F≤f/2 and N_v > f.
		Then A_v := N_v and B_v := Z_v.
		Therefore there exist at least f+1 nodes in A_v.
		Node v selects f+1 nodes A'_v from A_v by choosing all nodes from A_v ∩ F and the rest arbitrarily from A_v - F.

        Define B'_v := B_v ∩ (F - v).
        Now, B'_v≤B_v ∩ F = Z_v ∩ F≤f/2 by assumption of case 1.
		Since G is (3f/2+1)-connected, G - B'_v is at least (f+1)-connected and there exist f+1 node-disjoint A'_v v-paths in G - B'_v.
		Furthermore, since all the nodes in A_v ∩ F are endpoints in these paths and F = (A_v ∩ F) ∪ (B_v ∩ F), we have that these paths exclude F[Recall that a path that excludes X does not have nodes from X as internal nodes; however, nodes from X may be the endpoints of the path.].
		
		
  * Z_v ∩ F≤f/2 and N_v≤ f.
		Then A_v := Z_v and B_v := N_v.
		Note that when f = 0, this case is not possible since v ∈ B_v and so B_v = N_v must be non-empty.
		Since the degree of v is at least 2f and there are at most f nodes in B_v (including v), we have that v has at least f+1 neighbors in A_v.
		There are therefore f+1 node-disjoint A_v v-paths that have no internal nodes and hence exclude F.
		
		
  * Z_v ∩ F > f/2 and Z_v > f.
		Then A_v := Z_v and B_v := N_v.
		We have that
		
    N_v ∩ F   =      F - Z_v ∩ F
       ≤    f - f/2 - 1 
       ≤f/2.

		So this case is the same as Case 1 with the roles of Z_v and N_v swapped.
		
		
  * Z_v ∩ F > f/2 and Z_v≤ f.
		Then A_v := N_v and B_v := Z_v.
		From the analysis in Case 3, we have that N_v ∩ F≤f/2.
		So this case is the same as Case 2 with the roles of Z_v and N_v swapped.
	
	In all four cases we have that there do exist f+1 node-disjoint A_v v-paths that exclude F.



Lemma <ref>
	Fix a phase of the algorithm and the corresponding set F.
	For any node u, we denote the state at the beginning of the phase by γ_u^start and the state at the end of the phase by γ_u^end.
	Consider an arbitrary non-faulty node v and the sets A_v and B_v in step (c).
	If γ_v^start = γ_v^end, then the claim is trivially true.
	So suppose v ∈ B_v and v receives identical value along f+1 node-disjoint A_v v-paths that exclude F in step (a).

	Since the number of faulty nodes is at most f, thus at least one of these paths is both fault-free and has a non-faulty endpoint (other than v), say u.
	By Observation <ref>, it follows that whatever value is received by v along this path in step (a) is the value flooded by u.
	Therefore, γ_v^end = γ_u^start, where u is a non-faulty node, as required.



Lemma <ref>
	Fix a phase of the algorithm and the corresponding set F such that all faulty nodes are contained in F.
	Let Z be the set of nodes that flooded 0 in step (a) of the phase and let N be the set of nodes that flooded 1 in step (a).
	We first show that for any non-faulty node v, Z_v = Z and N_v = N.
	Consider an arbitrary node w ∈ Z (resp. w ∈ N) that flooded 0 (resp. 1) in step (a) of this phase.
	Observe that P_wv identified in step (b) of the phase excludes F and is fault-free.
	Therefore, by Observation <ref>, v receives 0 (resp. 1) along P_wv and correctly puts w in the set Z_v (resp. N_v), as required.
	
	It follows that for any two non-faulty nodes u and v, we have that Z_u = Z_v = Z and N_u = N_v = N.
	Thus A_u = A_v and B_u = B_v.
	Let A := A_u and B := B_u.
	First note that A is always non-empty as follows.
	If B is empty, then A = V is non-empty.
	If B is non-empty, then let w ∈ B be a node in B.
	By Lemma <ref>, there exist f+1 node-disjoint A w-paths, which implies that A≥ f+1.
	Now all nodes in A flooded identical value in step (a), say α.
	If u ∈ A, then u's state is α at the beginning of the phase and stays unchanged in step (c).
	Therefore, at the end of the phase γ_u = α.
	If u ∈ B, then observe that the f+1 node-disjoint A u-paths identified by u in step (c) are all fault-free.
	By Observation <ref>, it follows that u receives α identically along these f+1 paths and so, at the end of the phase, γ_u = α.
	Similarly for v, we have that γ_v = α, as required.

	
	

§ EFFICIENT ALGORITHM FOR 2F-CONNECTED GRAPHS
 
	
		
In this section we give an efficient algorithm when G is 2f-connected to prove Theorem <ref>.
We start by defining reliable message transmission.

 
	For two nodes u, v ∈ V, node v reliably receives a message flooded by node u if
	
		
  * u = v,
		
  * v is a neighbor of u, or
		
  * v receives the message identically on at least f + 1 node-disjoint uv-paths.
	


Observe that if a node u broadcasts a message M, then any node v cannot reliably receive a message M'  M from u.

We will say that a non-faulty node is a type A node if it knows the identity of all f faulty nodes.
Any non-faulty node that is not type A node is said
to be a type B node. 
Initially, all non-faulty nodes are type B nodes.
As the algorithm executes, some non-faulty nodes will discover the identity of all the faulty nodes and become type A nodes.







The algorithm proceeds in three phases.
In phase 1, each node v floods its input value.
As before, it requires v to first locally broadcast its input to its neighbors and then assist other nodes to flood their values by forwarding received messages from its neighbors.
Recall that flooding completes in n synchronous rounds.




In phase 2, v floods all the messages it hears from its neighbors in phase 1. Recall that under local broadcast model each node receives all the messages transmitted by its neighbors.
After n synchronous time steps, flooding in phase 2 will complete.

These messages help identify faulty nodes if they exhibit faulty behavior (i.e. tamper with messages).
The details are in the proof of Lemma <ref>.

In phase 3, type B nodes reach consensus and inform the type A nodes on the decision.
As discussed above, type A nodes can identify fault-free paths to each type B node.
If no type B node exists, then type A nodes decide by themselves.

The formal procedure is given in Algorithm <ref> and a proof of correctness follows.


		

		

The first lemma states that an adversary cannot hide a message broadcast by a faulty node.
 
	A message sent by a faulty node is received reliably by every node.



	Let u be an arbitrary faulty node and let v be an arbitrary node in G.
	If u = v or v is a neighbor of u, then the claim is trivially true from Definition <ref>.
	Otherwise, there exist 2f node-disjoint paths from u to v as the graph is 2f-connected.
	Since u is faulty, only f-1 of these paths can have faulty nodes.
	Any message sent by u is received identically by all its neighbors, and so v will receive it identically along the remaining f+1 node-disjoint paths that are fault-free.




Next, we want to show that all type B nodes know the same set of input values.
We need an intermediate lemma to show that.

 
	Let v and w be distinct nodes.
	In phase 1, if v reliably receives an input value of some node u and w does not, then v knows the identity of f faulty nodes after phase 2.



	Fix a node u with input b ∈ 0, 1 such that v reliably received b from u in phase 1 but w did not.
	Observe that, by Lemma <ref>, u is a non-faulty node since w did not reliably receive b from u in phase 1.

	Let P_1, …, P_2f be 2f node-disjoint uw-paths.
	Since w did not reliably receive b from u in phase 1, therefore exactly f of these paths have faulty nodes.
	WLOG let these paths be P_1, …, P_f.
	By Lemma <ref>, after phase 2, v reliably receives that some nodes on P_1 …, P_f forwarded b̅ = 1 - b in phase 1.
	For each path, v sets the first such node to be faulty.

	To see why this assignment of faulty nodes by v is correct, consider an arbitrary path in P_1, …, P_f.
	WLOG let this path be P_1.
	Let z be the faulty node in P_1 that tampers the message.
	Observe that each of P_1, …, P_f has exactly one faulty node that tampers the message.
	In phase 2, by Lemma <ref>, v reliably receives that z forwarded b̅ in phase 1.
	Moreover, let x be an arbitrary node in P_1 before z.
	Then x is non-faulty and forwarded b in phase 1.
	Therefore, in phase 2, v can not reliably receive that x forwarded b̅ in phase 1.


 
	All type B nodes reliably receive the same set of input values in phase 1.



	Suppose, for the sake of contradiction, that two nodes v and w are type B nodes and there exists a node u such that v reliably receives the input of u and w does not.
	Then, by Lemma <ref>, v knows the identity of f faulty nodes after phase 2.
	Therefore, v must be a type A node, a contradiction.


This next lemma shows that each node knows the input values of at least 2f other nodes.

 
	Each node reliably receives input values of at least 2f other nodes in phase 1.



	Since the graph is 2f connected, therefore each node has at least 2f neighbors.
	By Definition <ref> each node reliably receives input from these 2f nodes in phase 1.


We now have all the necessary lemmas to prove Theorem <ref>.

Theorem <ref>
	Each phase of Algorithm <ref> requires at most n synchronous rounds.
	Since there are only 3 phases, so the algorithm terminates in O(n) synchronous rounds.
	For validity and agreement, there are two cases to consider.

	There is at least one type B node:
	For agreement, note that by Lemma <ref> all type B nodes receive the same input values and therefore decide on the same value by taking the majority.
	A type A node (if one exists) knows the identity of all f faulty nodes and so it can ignore messages on paths with faulty nodes.
	So we only need one fault-free path between a type A node and any type B node.
	Since there are at least f node-disjoint fault free-paths between any two nodes, therefore in phase 3 each type A node correctly receives a message from a type B node about the final decision and decides on the same value.
	For validity, note that by Lemma <ref> each type B node has input values of at least 2f + 1 nodes (including its own).
	So the decided value is an input of at least f+1 nodes.
	Since there are at most f faulty nodes, therefore the decided value is an input of at least one non-faulty node, as required.


	There are no type B nodes:
	Let u be an arbitrary non-faulty node.
	Since there are no type B nodes, u is a type A node that does not receive any decision value from any type B node in phase 3.
	Since u knows the identity of f faulty nodes, u can identify fault-free paths to non-faulty nodes and receive untampered messages from non-faulty nodes in phase 1 and ignore messages from any path that contains a faulty node.
	Therefore, u knows the input values of all non-faulty nodes.
	For agreement, observe that all non-faulty nodes are type A and each non-faulty node decides on the same decision value by taking the majority of the input values of non-faulty nodes.
	For validity, all non-faulty nodes consider the input values of non-faulty nodes.

	



	    
	

§ PROOFS OF SECTION <REF>
 
	    This appendix pertains to the hybrid model.
		

 §.§ Necessity of the conditions in Theorem <ref>
 
			
 
	If there exists a Byzantine consensus algorithm under the hybrid model on a graph G tolerating at most f Byzantine faulty nodes, of which at most t nodes, 0 < t ≤ f, are equivocating faulty nodes,

	then every set of nodes S, such that 0 < |S| ≤ t, has at least 2f + 1 neighbors.





    Consider t such that 0 < t ≤ f.
	Let φ = f - t.
	For the sake of contradiction, suppose that there exists a non-empty set of nodes S in G of size at most t that has at most 2f neighbors and there exists an algorithm 𝒜 that solves Byzantine consensus under the hybrid model on G.
	Recall that neighbors of S are nodes outside of S that have an edge to some node in S.
	It is easy to show that when n > f ≥ t, each set of cardinality at most t must have at least one neighbor to achieve consensus.
	So in the rest of the proof we assume that S has at least one neighbor.
	Let N be the non-empty neighborhood of S.
	Then there exists a partition (F^1, F^2, R, T) of N such that F^1, F^2≤φ and R, T≤ t.
	Let W = V - (S ∪ N) be the set of remaining nodes.
	Note that some of these sets (other than S) can be possibly empty.
	However, since n > t and N is non-empty, we select these sets so that R is necessarily non-empty.
	Recall that 𝒜 outlines a procedure 𝒜_u for each node u that describes u's state transitions in each round.
	
	Similar to the proof of Lemma <ref>, we first create a network 𝒢 to model behavior of nodes in G in three different executions E_1, E_2, and E_3, which we will describe later.
	𝒢 consists of two copies of each node in W and T, and a single copy of the remaining nodes.
	Figure <ref> depicts 𝒢.
	The edges in 𝒢 can be deduced from Figure <ref> along the lines of the proof of Lemma <ref>.

	As in proof of Lemma <ref>, the structure of 𝒢 ensures that, for each edge uv in the original graph G, each copy of u receives messages from exactly one copy of v in 𝒢.
	This allows us to create an algorithm for 𝒢 corresponding to 𝒜 as follows.
	For each node u ∈ G, if 𝒢 has one copy of u then u runs 𝒜_u.
	Otherwise there are two copies u_0 and u_1 of u.
	Both u_0 and u_1 run 𝒜_u.
	
	
	
	Consider an execution ℰ of the above algorithm on 𝒢 as follows.
	Each node in W_0 ∪ T_0 ∪ F^1 ∪ S has input 0 and the remaining nodes have input 1.
	As in proof of Lemma <ref>, we will show that the algorithm does indeed terminate but nodes do not reach agreement in 𝒢, which will be useful in deriving the desired contradiction.
	We use ℰ to describe three executions E_1, E_2, and E_3 of 𝒜 on the original graph G as follows.
	
		
  * F^2 ∪ R is the set of faulty nodes and they are all non-equivocating faulty nodes.
		In each round, a faulty node in F^2 ∪ R broadcasts the same messages as the corresponding node in 𝒢 in execution ℰ in the same round.
		All non-faulty nodes have input 0.
		Note that the behavior of non-faulty nodes in S ∪ F^1, T, and W is modelled by the corresponding (copies of) nodes in S ∪ F^1, T_0, and W_0, respectively, in ℰ.

        Since 𝒜 solves Byzantine consensus on G, nodes in S ∪ F^1 ∪ T ∪ W decide on output 0 (by validity) in finite time.
		
		
  * F^1 is the set of non-equivocating faulty nodes and T is the set of equivocating faulty nodes.
		In each round, a non-equivocating faulty node in F^1 broadcasts the same messages as the corresponding node in 𝒢 in execution ℰ in the same round.
		Recall that a equivocating faulty node in T has the capability of point-to-point communication with its neighbors.
		The communication by equivocating faulty nodes in T to its neighbors in S is the same as that by the corresponding copy in T_0 and to the remaining non-faulty neighbors is the same as that by the corresponding copy in T_1 in execution ℰ.
		S has input 0 and all the remaining non-faulty nodes have input 1.
		Note that the behavior of non-faulty nodes in S ∪ F^2, R and W is modelled by the corresponding (copies of) nodes in S ∪ F^2, R, and W_1, respectively, in ℰ.

        The output of the non-faulty nodes will be described later.
		
		
  * F^1 ∪ S is the set of faulty nodes and they are all non-equivocating faulty nodes.
		In each round, a faulty node in F^1 ∪ S broadcasts the same messages as the corresponding node in 𝒢 in execution ℰ in the same round.
		All non-faulty nodes have input 1.
		Note that the behavior of non-faulty nodes in R ∪ F^2, T, and W is modelled by the corresponding (copies of) nodes in R ∪ F^2, T_1, and W_1, respectively, in ℰ.

        Since 𝒜 solves Byzantine consensus on G, nodes in F^2 ∪ R ∪ T ∪ W decide on output 1 (by validity) in finite time.
	
	



    Due to the output of nodes in S in E_1, the nodes in S output 0 in ℰ.
    Similarly, due to the output of nodes in R in E_3, the nodes in R output 1 in ℰ.
	It follows that in E_2, nodes in R as modeled by R in ℰ output 1 while S outputs 0.
	Recall that, by construction, both S and R are non-empty.
	This violates agreement, a contradiction.


 
	If there exists a Byzantine consensus algorithm under the hybrid model on a graph G tolerating at most f Byzantine faulty nodes, of which at most t are equivocating faulty nodes, then G is (3(f-t)/2 + 2t + 1)-connected.



	Suppose for the sake of contradiction that G is not (3(f-t)/2 + 2t + 1)-connected and there exists an algorithm 𝒜 that solves Byzantine consensus under the hybrid model on G.
	Let φ = f - t.
	Let C be a vertex cut of G of size at most 3φ/2  + 2t with a partition (A, B, C) of V such that A and B (both non-empty) are disconnected in G - C (so there is no edge between a node in A and a node in B).
	Since C≤3φ/2 + 2t, there exists a partition (C^1, C^2, C^3, R, T) of C such that C^1, C^2≤φ/2, C^3≤φ/2, and R, T≤ t.
	Recall that 𝒜 outlines a procedure 𝒜_u for each node u that describes u's state transitions in each round.
	
	Similar to the proof of Lemma <ref>, we first create a network 𝒢 to model behavior of nodes in G in three different executions E_1, E_2, and E_3, which we will describe later.
	𝒢 consists of two copies of each node in A, B, R, and T, and a single copy of the remaining nodes.
	Figure <ref> depicts 𝒢.
	The edges in 𝒢 can be deduced from Figure <ref> along the lines of the proof of Lemma <ref>.

	As in proof of Lemma <ref>, the structure of 𝒢 ensures that, for each edge uv in the original graph G, each copy of u receives messages from exactly one copy of v in 𝒢.
	This allows us to create an algorithm for 𝒢 corresponding to 𝒜 as follows.
	For each node u ∈ G, if 𝒢 has one copy of u then u runs 𝒜_u.
	Otherwise there are two copies u_0 and u_1 of u.
	Both u_0 and u_1 run 𝒜_u.
	
	
	
	Consider an execution ℰ of the above algorithm on 𝒢 as follows.
	Each node in A_0, B_0, R_0, T_0, and C^1 has input 0 and the remaining nodes have input 1.
	As in proof of Lemma <ref>, we will show that the algorithm does indeed terminate but nodes do not reach agreement in 𝒢, which will be useful in deriving the desired contradiction.
	We use ℰ to describe three executions E_1, E_2, and E_3 of 𝒜 on the original graph G as follows.
	
		
  * C^2 ∪ C^3 is the set of non-equivocating faulty nodes and T is the set of equivocating faulty nodes.
		In each round, a non-equivocating faulty node in C^2 ∪ C^3 broadcasts the same messages as the corresponding node in 𝒢 in execution ℰ in the same round.
		Recall that a equivocating faulty node in T has the capability of point-to-point communication with its neighbors.
		The communication by equivocating faulty nodes in T to its neighbors in A is the same as that by the corresponding copy in T_1 and to the remaining non-faulty neighbors is the same as that by the corresponding copy in T_0 in execution ℰ.
		All non-faulty nodes have input 0.
		Note that the behavior of non-faulty nodes in A, B, R, and C^1 is modelled by the corresponding (copies of) nodes in A_0, B_0, R_0, and C^1, respectively, in ℰ.

        Since 𝒜 solves Byzantine consensus on G, nodes in A ∪ B ∪ R ∪ C^1 decide on output 0 (by validity) in finite time.
		
		
  * C^1 ∪ C^3 is the set of non-equivocating faulty nodes and R is the set of equivocating faulty nodes.
		In each round, a non-equivocating faulty node in C^1 ∪ C^3 broadcasts the same messages as the corresponding node in 𝒢 in execution ℰ in the same round.
		The communication by equivocating faulty nodes in R to its neighbors in A is the same as that by the corresponding copy in R_0 and to the remaining non-faulty neighbors is the same as that by the corresponding copy in R_1 in execution ℰ.
		A has input 0 and all the remaining non-faulty nodes have input 1.
		Note that the behavior of non-faulty nodes in A, B, T, and C^2 is modelled by the corresponding (copies of) nodes in A_0, B_1, T_1, and C^2, respectively, in ℰ.

        The output of the non-faulty nodes will be described later.
		
		
  * C^1 ∪ C^2 is the set of non-equivocating faulty nodes and T is the set of equivocating faulty nodes.
		In each round, a non-equivocating faulty node in C^1 ∪ C^2 broadcasts the same messages as the corresponding node in 𝒢 in execution ℰ in the same round.
		The communication by equivocating faulty nodes in T to its neighbors in B is the same as that by the corresponding copy in T_1 and to the remaining non-faulty neighbors is the same as that by the corresponding copy in T_0 in execution ℰ.
		All non-faulty nodes have input 1.
		Note that the behavior of non-faulty nodes in A, B, R, and C^3 is modelled by the corresponding (copies of) nodes in A_1, B_1, R_1, and C^3, respectively, in ℰ.

        Since 𝒜 solves Byzantine consensus on G, nodes in A ∪ B ∪ R ∪ C^3 decide on output 1 (by validity) in finite time.
	
	



    Due to the output of nodes in A in E_1, the nodes in A_0 output 0 in ℰ.
    Similarly, due to the output of nodes in B in E_3, the nodes in B_1 output 1 in ℰ.
	It follows that in E_2, nodes in A as modeled by A_0 in ℰ output 0 while nodes in B as modeled by B_1 output 1.
	Recall that, by construction, both A and B are non-empty.
	This violates agreement, a contradiction.


We now prove the necessity of the conditions in Theorem <ref>.
The sufficiency is proved in the next section.

necessity of the conditions in Theorem <ref>
	Condition (i) follows from Lemma <ref>.
	For t = 0 condition (ii) follows from Lemma <ref> and for  t > 0 condition (iii) follows from Lemma <ref>.

		

 §.§ Sufficiency of the conditions in Theorem <ref>
 
			
In this section, we assume that the graph G satisfies the conditions in Theorem <ref>.
To prove sufficiency of the conditions in Theorem <ref>, we modify Algorithm <ref> for the hybrid setting.
The formal procedure is given in Algorithm <ref>.



For correctness, we follow the same ideas as the proof of Theorem <ref>.
We assume that t > 0 in the proof since Algorithm <ref> is the same as Algorithm <ref> when t = 0.
We follow the same strategy as in Section <ref>.

Let T^* be the actual equivocating faulty set of size at most t and F^* the actual non-equivocating faulty set of size at most f - T^*.

Similar to Observation <ref>, the following follows from the rules used for flooding.

 
	For any phase of Algorithm <ref>, in step (a) for any two nodes u, v ∈ V - T^* (possibly non-equivocating faulty), if v receives value b along a fault-free uv-path then u broadcast the value b to its neighbors during flooding.




The next two lemmas state that the paths identified in steps (b) and (c), respectively, do indeed exist.


    For any choice of sets F and T in Algorithm <ref>, and any two nodes u, v, there exists a uv-path that excludes F ∪ T.



    Recall that a path is said to exclude F ∪ T if none of the internal nodes in the path belong to F ∪ T.
    Since G is (3(f-t)/2+2t+1)-connected, by Menger's Theorem, there are at least (3(f-t)/2+2t+1) node-disjoint paths between any two nodes u, v.
	For any f, t such that 0 ≤ t ≤ f, we have that 3(f-t)/2+2t+1 ≥ (f - t) + t + 1 = f + 1.
	Thus, there are at least f+1 node-disjoint uv-paths, of which at least one path must exclude F ∪ T, since F ∪ T≤ f.



 
	For any non-faulty node v and any given phase of Algorithm <ref> with the corresponding sets F and T, in step (c), if v ∈ B_v, then there exist f+1 node-disjoint A_v v-paths that exclude F ∪ T.



	Fix a phase in the algorithm and the corresponding sets F and T.
	Let φ = f - T as in the algorithm.
	Consider an arbitrary non-faulty node v such that v ∈ B_v in step (c).
	There are 4 cases to consider, corresponding to the 4 cases in step (c).
	Note that neither A_v nor B_v contain any node from T.
	
		
  * Z_v ∩ F≤φ/2 and N_v > f.
		Then A_v := N_v and B_v := Z_v.
		Therefore there exist at least f+1 nodes in A_v.
		Node v selects f+1 nodes A'_v from A_v by choosing all nodes from A_v ∩ F and the rest arbitrarily from A_v - F.
        Define B'_v = B_v ∩ (F - v).
        Now, B'_v≤B_v ∩ F = Z_v ∩ F≤φ/2 by assumption of case 1.
		Since G is (3(f-t)/2+2t+1)-connected, the vertex connectivity of G - T - B'_v is at least
		
    3(f-t)/2 + 2t + 1 - T - φ/2   =  f - t + f-t/2 + 2t + 1 - T -  f - T/2
       =  1 + t + f-t/2 + f - T -  f - T/2
       =  1 + t + f-t/2 +  f - T/2
       ≥    1 + t + f-t/2 +  f - t /2
       =  f - t + t + 1   
       =  f + 1.

		So there exist f+1 node-disjoint A'_v v-paths in G-T-B'_v.
		Furthermore, since all the nodes in A_v ∩ F are endpoints in these paths and F = (A_v ∩ F) ∪ (B_v ∩ F), we have that these paths exclude[Recall that a path is said to exclude X if none of the internal nodes in the path belong to X.] F ∪ T.
		
		
  * Z_v ∩ F≤φ/2 and N_v≤ f.
		Then A_v := Z_v and B_v := N_v.
		Recall that 0 < t ≤ f and F≤φ.

		Let F' be a maximal set such that
		
			
  * F' ⊆ B_v - v,
			
  * F' ⊇ (F ∩ B_v) - v, and
			
  * F'≤φ,
		
		i.e., there is no set F”⊇ F' such that
		
			
  * F”⊆ B_v - v,
			
  * F”⊇ (F ∩ B_v) - v, and
			
  * F”≤φ.
		
		Note that F' exists because F≤φ.
		Let B'_v = B_v - F'.
		We first show that B'_v≤ t.
		There are two cases to consider.
		In the first case, F' < φ.
		Then v is the only node in B'_v = B_v - F' as follows.
		Suppose there is another node u ∈ B'_v = B_v - F'.
		Then F' ∪u⊆ B_v - v and F' ∪u⊇ F' ⊇ (F ∩ B_v) - v.
		Moreover, F' ∪u = F' + 1 ≤φ, a contradiction since F' is maximal.
		So we have that B_v' = 1 ≤ t.
		In the second case, F' = φ, and we have that B_v' = B_v - φ = N_v - φ≤ f - φ = T≤ t.
		
		We construct a graph H from G - T - F' as follows.
		Remove all edges uw such that both u, w ∈ A_v.
		Add a node r with edges to all nodes in A_v.
		We first show that H has f+1 node-disjoint rv-paths.
		So suppose, for the sake of contradiction, that H does not have f+1 node-disjoint rv-paths.
		Then by Menger's Theorem, there exists an rv-cut C of size at most f.
		This partitions H - C into (R, S) such that R and S are both non-empty and disconnected with r ∈ R and v ∈ S.
		Since r has an edge to each node in A_v, we have that S ⊆ B_v' and so S≤ t.
		All the neighbors of S in H are contained entirely in C[Recall that neighbors of S are nodes outside of S that have an edge to some node in S.].
		Since no edge incident to any node in B_v' in G was removed when constructing graph H, so all the neighbors of S in G are contained entirely in C ∪ T ∪ F'.
		It follows that S has at most f + T + φ = f + T + f - T = 2f neighbors in G, a contradiction with the condition (iii) in Theorem <ref>.
		
		We now show that f+1 node-disjoint rv-paths in H imply that there are f+1 node-disjoint A_v v-paths in G that exclude F ∪ T.
		Observe that an rv-path P in H can have more than one node from A_v.
		However, since r has an edge to each node in A_v, a shorter sub-path P' exists that contains only the last node from A_v in P.
		Furthermore, if a path Q and P are node-disjoint, then so are Q and P'.
		So there exist f+1 node-disjoint rv-paths that each contain exactly one node from A_v.
		By removing the endpoint r from each of these paths, we get f+1 node-disjoint A_v v-paths.
		Since each of these paths have exactly one node from A_v, this must necessarily be an endpoint.
		So each of these paths exclude A_v.
		By construction of H, these paths exist in G - T - F' and so exclude F' and T as well.
						
		Now, A_v ⊇ A_v ∩ F and F = (A_v ∩ F) ∪ (B_v ∩ F).
		Recall that F' ⊇ (B_v ∩ F) - v.
		It follows that the f+1 node-disjoint A_v v-paths above exclude A_v ∪ F' ∪ T ⊇ (F - v) ∪ T.
		Since v can only be an endpoint in these paths, we have that these f+1 node-disjoint A_v v-paths exclude F ∪ T, as required.
		
		
  * Z_v ∩ F > φ/2 and Z_v > f.
		Then A_v := Z_v and B_v := N_v.
		We have that
		
    N_v ∩ F   =      F - Z_v ∩ F
       ≤φ - φ/2 - 1 
       ≤φ/2.

		So this case is the same as Case 1 with the roles of Z_v and N_v swapped.
		
		
  * Z_v ∩ F > φ/2 and Z_v≤ f.
		Then A_v := N_v and B_v := Z_v.
		From the analysis in Case 3, we have that N_v ∩ F≤φ/2.
		So this case is the same as Case 2 with the roles of Z_v and N_v swapped.
	
	So we have that there do exist f+1 node-disjoint A_v v-paths that exclude F ∪ T.


The next lemma states that in any phase, the state of a non-faulty node at the end of the phase equals the state of some non-faulty node at the beginning of the phase.

 
	For any non-faulty node v, its state γ_v at the end of any given phase equals the state of some non-faulty node at the start of that phase.



	Fix a phase in the algorithm and the corresponding sets F and T.
	For any node u, we denote the state at the beginning of the phase by γ_u^start and the state at the end of the phase by γ_u^end.
	Consider an arbitrary non-faulty node v and the sets A_v and B_v in step (c).



	If γ_v^start = γ_v^end, then the claim is trivially true.
	So suppose v ∈ B_v and v receives identical value along f+1 node-disjoint A_v v-paths in step (a).
	Since the number of faulty nodes is at most f, at least one of these paths is both fault-free and has a non-faulty endpoint (other than v), say u.
	By Observation <ref>, it follows that whatever value is received by v along this path in step (a) is the value flooded by u.
	Therefore, γ_v^end = γ_u^start, where u is a non-faulty node, as required.


Next, we show that when the sets F and T are properly selected, all non-faulty nodes reach agreement in that phase.

 
	Consider the unique phase of the Algorithm <ref> where F = F^* and T = T^*.
	At the end of this phase, every pair of non-faulty nodes u, v ∈ V have identical state, i.e., γ_u = γ_v.



	Consider the unique phase of the algorithm where F = F^* and T = T^*.
	By choice of T, all equivocating faulty nodes are in T so each node in V - T floods one value, and one value only, in step (a) of the phase.
	Let Z ⊆ V - T be the set of nodes that flooded 0 in step (a) and let N ⊆ V - T be the set of nodes that flooded 1 in step (a).
	We first show that for any non-faulty node v, Z_v = Z and N_v = N.
	Consider an arbitrary node w ∈ V - T that flooded 0 (resp. 1) in step (a) of this phase.
	Note that w ∈ Z (resp. w ∈ N).
	Observe that P_wv identified in step (b) of the phase excludes T ∪ F and is fault-free.
	Therefore, by Observation <ref>, v receives 0 (resp. 1) along P_wv and correctly puts w in the set Z_v (resp. N_v), as required.
	
	It follows that for any two non-faulty nodes u and v, we have that Z_u = Z_v = Z and N_u = N_v = N.
	Thus A_u = A_v and B_u = B_v.
	Let A := A_u and B := B_u.
	Since T = T^* has no non-faulty node, a non-faulty node is either in A or in B.
	First note that A is always non-empty as follows.
	If B is empty, then A = V - T is non-empty since n > f.
	If B is non-empty, then let w ∈ B be a node in B.
	By Lemma <ref>, there exist f + 1 node-disjoint Aw-paths, which implies that A≥ f + 1.
	Now all nodes in A flooded identical value in step (a), say α.
	If u ∈ A, then u's state is α at the beginning of the phase and stays unchanged in step (c).
	Therefore, at the end of the phase γ_u = α.
	If u ∈ B, then observe that the f+1 node-disjoint A u-paths identified by u in step (c) are all fault-free.
	By Observation <ref>, it follows that u receives α identically along these f+1 paths and so, at the end of the phase, γ_u = α.
	Similarly for v, we have that γ_v = α, as required.


We now have all the necessary ingredients to prove the sufficiency portion of Theorem <ref>.

Theorem <ref>
    The necessity of the conditions in Theorem <ref> were proven in Appendix <ref>.
    For sufficiency, we prove the correctness of Algorithm <ref>.
    
    The algorithm terminates in finite time because the number of phases is finite and flooding in each phase completes in finite time.
	Thus, the algorithm satisfies the termination condition.
	
	Since there are at most f faulty nodes with at most t equivocating faulty nodes in any given execution, there exists at least one phase in which sets F = F^* and T = T^*.
	Then, from Lemma <ref>, we have that all non-faulty nodes have the same state at the end of this phase.
	Lemma <ref> implies that the state of the non-faulty nodes will remain unchanged after any subsequent phases.
	Therefore, all non-faulty nodes will have the same state at the end of the algorithm, and their output will be identical.
	This proves that the algorithm satisfies the agreement condition.
	
	At the start of phase 1, the state of each non-faulty node equals its own input.
	Now, applying Lemma <ref> inductively implies that the state of a non-faulty node always equals the input of some non-faulty node.
	This, in turn, implies that the algorithm satisfies the validity condition.
	Thus, we have proved correctness of Algorithm <ref> under the conditions stated in Theorem <ref>.

			
			
