ByzantinE Resistant GEometric Routing
WiP: Work in Progress

Table of Contents

Anything marked with a 1 is awaiting verification by Prof. Nesterenko or Prof. Sharma.

1. Overview

We have a network (graph), \(G\), of nodes that know only the current message, their position, and the set of their neighbors’ positions. They do not have space for routing tables, nor space to store information about messages that pass through them. The goal is to route a message from \(s\) to \(t\) such that \(t\) will decode the correct message even in the presence of 1 node that behaves arbitrarily (i.e. is Byzantine).

The simplest solution without a Byzantine node would be to greedy route; at each step going to the node geometrically closest to \(t\). However, local minima result in this naïve algorithm not reaching \(t\). A guaranteed solution is to include draw a line through \(s\) and \(t\) (encoded in the message), and then route along all edges of any face that intersects the \(s-t\) line. This was done in Concurrent Face Routing (CFR) (Clouser, Miyashita, and Nesterenko 2012) and is adapted here as the “cores” of our braided routing algorithm.

The state of the art1 in geographic routing is GOAFR+ (Kuhn et al. 2003) where they route packets within an ellipse, increasing the size of the ellipse if progress is not made. They demonstrate practical efficiency and prove their algorithm is asymptotically optimal in the worst-case: \(O(p^2)\), where \(p\) is the shortest path length from \(s\) to \(t\), and we assume a unit-disk graph (UDG). We attempted something similar, but were stymied by networks that had multiple external faces on the \(s-t\) line; we may attempt this again assuming no such intersections.

Finally, (Friedman et al. 2007) proves a correspondence between interactive consensus conditions (ICCs) and error-correcting codes (ECCs). But I believe the ICCs apply to broadcast networks1 (complete graphs), so are not directly applicable here.

2. Mathematical Formalism

See also: 8.1

Formally, each node, except for 1, uses the same routing algorithm, \( f \), that takes a message, \(m \in M\), the proximal source of the message, \(\mathbf v_{-1}\), the current node’s position \(\mathbf v_0\), and the set of the current node’s neighbors’ positions \(\mathbf V\) and returns a set of (possibly modified) messages along with the node to pass each message to: \[ f: m, \mathbf v_{-1}, \mathbf v_0, \mathbf V \mapsto \{ (m \in M, \mathbf v) : \forall m, \mathbf v \in \mathbf V \} \]

Alternatively, you can imagine that there is a copy of \( G \), \( G_m \), for every \( m \). We will call the union of these \(G_M\). Changing a message from \(m_1\) to \(m_2\) is now expressed as moving it from \(G_{m_1}\) to \(G_{m_2}\). Now \(f\) forms a path-sensitive directed graph:

\[ f: \mathbf v_{-1}, \mathbf v_0, \mathbf v_M \mapsto \mathcal P( \mathbf V_M ) \]

Which is a directed graph, modified to be sensitive to the proximal source of the message. More formally, a directed graph, \(G\), is defined by an ordered pair of a set of vertices and set of arches \((V, A)\), and an arch is defined as an ordered pair of vertices. I define a path-sensitive graph similarly, but with \(A\) being an ordered triple of vertices.

It is critical that this graph is acyclic, otherwise our algorithm will not terminate.

Our solution only uses very weak assumptions. E.g. We only use the message for the \(s-t\) line, chirality (whether the message will take the next available CW node, or CCW node), and a single excluded node. So their may be some way to simplify the above to a directed graph. We only use the positions of nodes (along with the \(s-t\) line encoded in the message) to exclude neighbors on the other side of the source-target line. So we reduce all the GPS information down to 1 bit per edge.

3. Assumptions

Click an item to expand its subtree.

3.1. polyhedral (3-connected & planar)

If the network is strictly 1-connected, there exists a path along which a single Byzantine node cannot be detected.

If the network is strictly 2-connected, there exists two paths from \( s \) to \( t \) along which a single Byzantine node can be detected, but not mitigated, as we cannot know which of the 2 paths to trust.

If the network is 3-connected, you are able to mitigate a single Byzantine node. The simplest way to do this is by routing along 3 disjoint paths and taking the majority.

We assume the network is planar for convenience. There exist techniques to planarize a network.

3.2. The Triconnectivity Assumption

The graph remains 3-connected after removing all edges that intersect the \(s-t\) line.

3.3. infinite bandwidth

3.4. nodes know their position

3.5. nodes know their neighbors’ positions (even if Byzantine)

3.6. source node knows target node’s position

3.7. no nodes lie on the source-target line, WLoG

We can simply modify the algorithm to assume nodes on the source-target line are to the right of the source-target line.

3.8. one faulty node (cannot be \(s\) or \(t\))

3.9. we use a source-target line segment

4. Potential Additional Assumptions

Below are some additional assumptions that we could make if they lead to a nice solution.

4.1. the \(s-t\) line does not intersect an external face

4.2. alternatively: nodes can tell if they lie on the external fice 1

4.3. message size is logarithmic in the number of nodes 1

4.4. we have a unit-disk graph

In practice, nodes are usually communicating wirelessly.

5. Facts

5.1. Our nodes are not embedded in Euclidean space

We only use geometry locally to the source-target line (for the junction nodes), so we use very few properties of the metric space. In particular, we could embed our graph in elliptical space.

5.1.1. Imagining the network on a ball can be more intuitive

  1. PROVE In particular, there is no distinction between an internal and external face.

    In particular, there is no online way a node can tell that it is on an external face.

5.1.2. PROVE Source-target line can be any arbitrary path

5.2. Polyhedral graphs can be represented as a polyhedron

5.3. Polyhedral graphs have a unique dual graph that is also polyhedral

  • The nodes are the faces of the primal polyhedral graph.
  • This is an involution 2


Figure 1: The cube and octahedron are duals of each other.

5.4. Polyhedral faces share <3 nodes in common

5.4.1. Junction nodes on blue faces are always consecutive

5.5. PROVE once we venture further than a blue face, we are lost

5.6. PROVE counting non-green nodes is not useful

6. Definitions

6.1. green face: a face that intersects the source-target line segment

6.2. green node: a node that lies on the green face

6.3. blue face: a face adjacent to a green face

6.4. junction: a node that has a neighbor across the source-target line

Junctions are the only ones who know their color. All other nodes rely on them in some way for position information.

6.5. interchange: an edge that crosses the \(s-t\) line

Alternatively, an edge connecting two junctions.

6.6. highway: all green nodes between two consecutive junctions

6.7. mitigate (a node): achieve safety and liveness even if the node is Byzantine

6.8. recoverable: the algorithm generalizes optimally to non-3-connected graphs

i.e. the algorithm mitigates a node iff it is possible to mitigate the node

%%{init: {'theme':'neutral'}}%%
graph LR

 style B fill:#ffcdd2
 style E fill:#ffcdd2



6.8.1. PROVE a node can be mitigated iff its neighbors are 3-connected to each other

7. Cores

We form 2 disjoint paths from the faces that intersect the \(s-t\) line segment. This can include the external face. We do this by routing 2 chiral packets: \(p_\text{CCW}\) is sent from \(s\) to the first clockwise node and from then on will always take the first available counter-clockwise node. A node is available iff the edge to it does not intersect the \(s-t\) line segment. \(p_\text{CW}\) is the same, but symmetric.

We call \(p_\text{CW}\) and \(p_\text{CCW}\) the cores because they form the core of our braided routing algorithm by mitigating non-green nodes:

Assuming only 1 Byzantine node, if the target receives matching green packets from both of target’s green neighbors, we know that these messages took disjoint paths and so must be correct. So from now on we can consider the case where only green nodes are Byzantine.

7.1. PROVE this works by induction

  1. Each point between the source and target is either an edge or a face.
  2. Each edge must end in exactly one node right of the target line and one node left of it.
  3. By 2-connectivity, any node of a face can reach any other node via two paths.
  4. This implies that there are disjoint paths between the 2 nodes left of the target line and the 2 nodes right of the target line.
  5. By 3-connectivity, no faces can share more than 1 edge or more than 2 nodes.
  6. By construction, the 2 shared nodes are the ones whose edge crosses the source-target line segment

7.2. PROVE that we can avoid non-green nodes sending green messages

The above works assuming green nodes never forward green packets from non-green nodes. At first glance, this appears to be evident from the fact that a packet is green is encoded in the traversal direction and which side of the source-target line the current node is on. However:

  1. only junction nodes are aware which side of the source-target line segment they’re on
  2. only junction nodes are aware they’re green
  3. only junction nodes know which of their neighbors are green

I think traversal direction will result in no non-green messages getting mixed in with the genuine green messages.

8. Braiding

Now, we need to modify one side of the source-target line such that either:

  1. No more than 1 vertex to the target carries an incorrect message, or
  2. One correct message arrives. Because if target sees equivocation on one side of the source-target line, it knows the other side is correct.

The idea is that we will braid around green nodes, so in addition to sending a message A → B → C → D, we will also send A → C and B → D:

%%{init: {'theme':'neutral'}}%%
graph LR

Braiding is implemented by the core not only sending a packet to the next green node, but also sending a packet to bypass that node. It does this by adding the next green node to a “bypass” field in the message and then routing it around the blue face (see 13.4). This message is routed the same as a core, except that, in addition to nodes across the \(s-t\) line, the bypassed node is also not considered an available node.

This is quadratic w.r.t core length. It is not exponential because a node does not create new braids for messages that contain a bypass field, and the bypass field is never removed. This does not cause issues because if \(b_i\) bypasses node \(i\), then either:

  1. \(i\) was Byzantine, in which case we can assume that no further nodes are Byzantine and core routing the rest of the way will succeed, or
  2. \(i\) was not Byzantine, in which case \(b_i\) provides no useful information.

8.1. Pseudocode

We assume that nodes are identified by their GPS coordinates, i.e. are a vector in 2d. For convenience, we will order \( \mathbf V \) such that \( \mathbf V_0 \) is the proximal source of the message, \( V_1 \) is the next neighbor clockwise from \( \mathbf V_0 \), etc. WLoG, we assume no two neighbors lie at the same angle.

Input: \(m\), the content of the message,
Input: \(\mathbf s\), the source of the message,
Input: \(\mathbf t\), the target of the message,
Input: \(\mathbf b\), a node to be bypassed (initially none),
Input: \( \mathbf v \), the current node, and
Input: \(\mathbf V_0\), the proximal source of the message,
Input: \( \mathbf N_{\mathbf v} \), the set of neighbors of the current node.
Output: A set of packets:
    \(m'\), the content of the forwarded message,
    \(\mathbf V_n\), the node to forward the message to

  1. function BeRGeR\((m, \mathbf s, \mathbf t, \mathbf b, \mathbf v, \mathbf V_0, \mathbf N_{\mathbf v})\)
  2.     st ← line(m.source,
  3.     for \( \mathbf V_n \) in \( \mathbf V \):
  4.         if \( \mathbf V_n \) is on the other side of st:
  5.             continue
  6.         BeRGeR\((m, \mathbf s, \mathbf t, \mathbf b, \mathbf n, \mathbf v, \mathbf N_{\mathbf n})\)
  7.         if \( \mathbf b \) == \( \emptyset \):
  8.             BeRGeR\(( m, \mathbf s, \mathbf t, \mathbf n, \mathbf V_{n+1}, \mathbf v, \mathbf N_{n+1} )\)

8.2. PROVE braiding terminates

8.3. PROVE braiding terminates in the presence of Byzantine nodes

8.3.1. TODO consider cases of Byzantine nodes that forge messages from scratch

9. QUESTION How can we improve the message complexity of braiding?

Ideally we would like to send 2 braids: one which skips odd green nodes, and another which skips even green nodes. It does not seem that this is possible, at best I believe we need a number of braids proportional to the maximum number of nodes on a green face. But I strongly suspect a solution better than quadratic.

9.1. DRAFT NOTES: How can braiding mitigate consecutive junction nodes

Naïve braiding will lead to pile ups around the junction nodes, causing braiding to fail: both braids touch the same green node. To avoid this, we can send many different types of braids: Some will take 1 step along a green face before leapfrogging, some will take 2, some will take 3, 4, …, j, where j is the maximum number of consecutive junction nodes.

9.1.1. I suspect there is a way to do this that is \(O(n \log n)\) instead of \(O(n^2)\) in the worst case

Perhaps by using the total count of green nodes traversed, modular arithmetic, prime numbers, … ?

10. 2 Cores, 4 snakes, and 4 dogs

We partition the graph into cores/non-cores. Then we form 2 orthogonal partitions within cores, left/right and junctions/highways.

  1. Cores: the set of all nodes on a face intersecting the \(s-t\) line
    1. Left/Right
      1. Left (North): CW core
      2. Right (South): CCW core
    2. Junctions/Highways
      1. Junction: A node that has a neighbor across the \(s-t\) line, excluding junctions whose only highways connect to earlier junction nodes. The order is determined by the interchange that intersects the \(s-t\) line closest to \(s\)
      2. Highway: A set of green nodes between two consecutive junction nodes. May be empty.

So we have partitioned the graph into: \(H_L, H_R, J_L, J_R\). We can further subdivide it into \(H_{L0}, H_{L1}, ..., H_{R0}, H_{R1}, ..., J_{L0}, J_{L1}, ..., J_{R0}, J_{R1}, ...\), which we will refer to as our partitions.

We have developed simple algorithms that will visit partitions in a particular pattern as shown in the table below.

  1. Left/right cores stick to their respective side.
  2. 0-snakes (not included in the table) work like cores, except they cross and change chirality at each junction node. After crossing, they exclude all junction nodes that neighbor the vertices of the interchange they just crossed. This has the effect of simplifying the graph such that each junction has exactly one interchange.
  3. 1-snakes work the same, except they cross every other junction. The even snake \(S_0\) will cross at even interchanges.
  4. TODO: explain algorithm for dogs
Table 1: Between each pair of horizontal lines is 1 path, represented by as a set of partitions.
I believe each path is equivalent to 1 codeword.
left nodes of L   HL0 JL1 HL1 JL2 HR2 JR3 HR3 JL4 HL4 JL5 HL5 JL6  
right nodes L                            
left nodes R                            
right nodes of R   HL0 JL1 HL1 JL2 HR2 JR3 HR3 JL4 HL4 JL5 HL5 JL6  
left nodes of S0L   HL0 JL1 HL1 JL2       JL4 HL4 JL5 HL5 JL6  
right nodes of S0L         JR2 HR2 JR3 HR3 JR4       JR6  
left nodes of S0R         JL2 HL2 JL3 HL3 JL4       JL6  
right nodes of S0R   HR0 JR1 HR1 JR2       JR4 HR4 JR5 HR5 JR6  
left nodes of S1L   HL0 JL1       JL3 HL3 JL4 HL4 JL5      
right nodes of S1L     JR1 HR1 JR2 HR2 JR3       JR5 HR5 JR6  
left nodes of S1R     JL1 HL1 JL2 HL2 JL3       JL5 HL5 JL6  
right nodes of S1R   HR0 JR1       JR3 HR3 JR4 HR4 JR5      
left nodes of D0L   HL0 JL1   JL2 HL2 JL3   JL4 HL4 JL5   JL6  
right nodes of D0L   HR0   HR1 JR2 HR2   HR3 JR4 HR4   HR5 JR6  
left nodes of D0R   HL0   HL1 JL2 HL2   HL3 JL4 HL4   HL5 JL6  
right nodes of D0R   HR0 JR1   JR2 HR2 JR3   JR4 HR4 JR5   JR6  
left nodes of D1L     JL1 HR1 JL2   JL3 HL3 JL4   JL5 HL5 JL6  
right nodes of D1L   HR0 JR1 HR1   HR2 JR3 HR3   HR4 JL5 HR5    
left nodes of D1R   HL0 JL1 HR1   HL2 JL3 HL3   HL4 JL5 HL5    
right nodes of D1R     JR1 HR1 JR2   JR3 HR3 JR4   JL5 HR5 JR6  

The even left dog, \(D_{0L}\), hits only even junction nodes on the right. The odd left dog, \(D_{1L}\), hits only odd junction nodes on the right.

We are exploring a new type of path that partitions the network into forward/rear parts.

11. Modulo Braiding

An alternative way of braiding is to assume all nodes have an arbitrary ID. This could be their GPS coordinates, a hash of their GPS coordinates, or anything else.

Now we send out 5 braids: \(b_i\) will bypass \(\mathbf v\) iff \( \mathrm{ID}(\mathbf v) = i \mod 5 \).

More generally, we can send out n braids: \(b_i\) will skip \(\mathbf v\) iff \( \mathrm{ID}(\mathbf v) = i \mod n \)

This guarantees that for all \(\mathbf v\), there is a braid that bypass it. The probability that \(b_i\) will bypass a node with a random ID is \(b^{-1}\). Delivery is not guaranteed because you could have a wall of nodes that are all equal, mod 5; however, I believe in this case, braids will eventually return to \(s\), which can then send more braids.

%%{init: {'theme':'neutral'}}%%
graph LR
 subgraph 1[" "]
 subgraph 2[" "]
 style 1 opacity:0
 style 2 opacity:0

We can touch only one core, so that leaves us with a 2-connected network, which I believe in the worst case looks like the above: The packet has only two options to progress forward: Either go directly forward, or go sideways and then forward. So at each step, the probability of being blocked at that step is:

\begin{align*} 1 - p &= n^{-1} \times (1 - (1-n^{-1})^2) \\ &= 2n^{-2} - n^{-3} \end{align*}

And the probability of not being blocked after \(d\) steps is:

\[ p^d = (1-2n^{-2}+n^{-3})^d \]

which means if we hold \(p\) fixed, \(n\) is a sublinear function of \(d\).

If this is correct, the number of braids required using this naïve approach is sublinear in distance, meaning the congestion is subquadratic compared to the core.

Unfortunately, this relies on the assumption that the other green path is on the other side of the \(s-t\) line (i.e. the \(s-t\) line segment does not intersect an external face).

11.1. TODO check my working above

11.2. PROVE that braids return to sender

11.3. PROVE that this is indeed the worst case

12. TODO [0/5]

12.1. TODO prove algorithm terminates in case of a Byzantine node

even if the Byzantine node pretends to be good by delivering the correct message to target.

12.2. TODO (briefly) check if algorithm works for 2 faults on 5-connected graphs

12.3. TODO see if it can be used to geocast

12.5. TODO consider other possible attacks

12.5.1. Deception about the face color

12.5.2. Deception about the target line

  1. PROVE Equivocating about target line does not help an attacker

13. Other ideas

13.1. Better Braiding

Our braiding above is asymmetric: We use HFR on both sides, then we braid one side. The asymmetric solution may work better for small networks, but I expect a much nicer solution exists by dumping HFR in favor of a 5-braid where no 3 strands can contain the same node.

Such a braid may have much higher latency though, especially in the case where no green nodes are Byzantine and HFR is almost optimal.

It also may be very hard to create on online algorithm to create a 5-braid. There’s a reason ladies typically braid their hair with 2 or 3-braids. 5-braiding is not easy. And online routing demands we do it with our eyes closed!


Figure 2: Braided hairstyles.

The ladder braid shows potential for research as it does use 5 strands and the rungs could represent the edges of our graph that cross the source-target line. Unfortunately, it does have quadratic complexity.

13.2. Can we use order that messages arrive at target?

13.3. distributed graph coloring (Maus 2021)

13.4. “routing around the blue face” may be equivalent to routing around the link of a simplicial complex


Figure 3: Link of a simplical complex.

13.5. Misha’s ideas:

13.5.1. Newton’s polytopes

13.5.2. rigorously define the problem

13.5.3. speak to Jenya

13.5.4. speak to Fedya

14. Citations

Clouser, Thomas, Mark Miyashita, and Mikhail Nesterenko. 2012. “Concurrent Face Traversal for Efficient Geometric Routing.” Journal of Parallel and Distributed Computing 72 (5): 627–36.
Friedman, Roy, Achour Mostefaoui, Sergio Rajsbaum, and Michel Raynal. 2007. “Asynchronous Agreement and Its Relation with Error-Correcting Codes.” Ieee Transactions on Computers 56 (7): 865–75.
Kuhn, Fabian, Rogert Wattenhofer, Yan Zhang, and Aaron Zollinger. 2003. “Geometric Ad-Hoc Routing.” Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing, July.
Maus, Yannic. 2021. “Distributed Graph Coloring Made Easy.” 2021.



Awaiting verification by Prof. Nesterenko or Prof. Sharma.


The dual of the dual is the primal.

Author: Mikhail Nesterenko, Zaz B

Created: 2024-05-22 Wed 11:52