BeRGeR
ByzantinE Resistant GEometric Routing
WiP: Work in Progress

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 art¹ 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 networks¹ (complete graphs), so are not directly applicable here.

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.

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

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.

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
 A((A))-..->C((C))
 A((A))-->B((B))
 B((B))-->C((C))
 C((C))-->D((D))
 B((B))-..->D((D))

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.

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.

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

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.

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
 s((s))---A((A))
 s---E((E))
 subgraph 1[" "]
   A---B((B))
   B---C((C))
   C---D((D))
 end
 subgraph 2[" "]
   E---F((F))
   F---G((G))
   G---H((H))
 end
 A---E
 B---F
 C---G
 D---t((t))
 H---t
 D---H
 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:

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).