BeRGeR
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 st 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(p2), 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 st 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, mM, the proximal source of the message, v1, the current node’s position v0, and the set of the current node’s neighbors’ positions V and returns a set of (possibly modified) messages along with the node to pass each message to: f:m,v1,v0,V{(mM,v):m,vV}

Alternatively, you can imagine that there is a copy of G, Gm, for every m. We will call the union of these GM. Changing a message from m1 to m2 is now expressed as moving it from Gm1 to Gm2. Now f forms a path-sensitive directed graph:

f:v1,v0,vMP(VM)

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

5. Facts

5.2. Polyhedral graphs can be represented as a polyhedron

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.6. highway: all green nodes between two consecutive junctions

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

7. Cores

We form 2 disjoint paths from the faces that intersect the st line segment. This can include the external face. We do this by routing 2 chiral packets: pCCW 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 st line segment. pCW is the same, but symmetric.

We call pCW and pCCW 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.

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
 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 st 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 bi 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 bi provides no useful information.

8.2. PROVE braiding terminates

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.

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 st 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 st line, excluding junctions whose only highways connect to earlier junction nodes. The order is determined by the interchange that intersects the st 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: HL,HR,JL,JR. We can further subdivide it into HL0,HL1,...,HR0,HR1,...,JL0,JL1,...,JR0,JR1,..., 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 S0 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, D0L, hits only even junction nodes on the right. The odd left dog, D1L, 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: bi will bypass v iff ID(v)=imod5.

More generally, we can send out n braids: bi will skip v iff ID(v)=imodn

This guarantees that for all v, there is a braid that bypass it. The probability that bi will bypass a node with a random ID is b1. 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:

1p=n1×(1(1n1)2)=2n2n3

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

pd=(12n2+n3)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 st line (i.e. the st 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.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

13. Other ideas

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

13.3. distributed graph coloring (Maus 2021)

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. https://doi.org/10.1016/j.jpdc.2012.01.009.
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. https://doi.org/10.1109/tc.2007.1043.
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. https://doi.org/10.1145/872035.872044.
Maus, Yannic. 2021. “Distributed Graph Coloring Made Easy.” 2021.

Footnotes:

1

Awaiting verification by Prof. Nesterenko or Prof. Sharma.

2

The dual of the dual is the primal.

Author: Mikhail Nesterenko, Zaz B

Created: 2024-05-22 Wed 11:52