Geometric Routing Concepts and Byzantine Fault Tolerance
undefined
BeRGeR: Byzantine-Robust
Geometric Routing
Zaz Brown
Mikhail Nesterenko
Gokarna Sharma
May
29-31
,
2024
Rabat, Morocco
•
static nodes, each node knows its global coordinates, source knows
coords
of
target
•
little overhead
▪
no routing tables
:
each node only knows coords of neighbors
▪
no memory
:
no info kept at node after message is routed
▪
no global knowledge
•
simple approaches
▪
flooding – expensive
▪
greedy routing
−
message carries coords of
target
−
each node forwards to neighbor closer to
destination
▪
problem:
local minimum
−
what if no closer neighbor?
▪
use face routing on planar graph
Geometric Routing: Routing without Overhead
Geometric Routin
g with Byzantine Faults
problem:
•
Byzantine fault
: arbitrary node behavior, hardest to counter, can model either faults or intruders
•
in general, requires 2f+1 connectivity
•
can we find 3 disjoint paths offline? Byzantine node resists topology discovery
question:
•
can we do geometric routing with Byzantine fault?
solution:
BeRGeR: Byzantine-Robust Geometric Routing
algorithm
•
single Byzantine fault
•
3-connected planar graph (more details later)
Outline
Graph Terms
•
unit disk graph
:
two vertices are adjacent iff they are within unit distance
▪
approximates radio model
•
planar
(embedding) graph
–
can be effectively constructed from a unit disk graph
•
source (
s
),
target
(
t
) vertices,
s
t
-line
▪
coords assumed carried by message
•
face
:
area where any two points can
be connected by a line not
intersecting graph edges
▪
single infinite external face
Routing Terms and Assumptions
•
right-hand-rule
:
if node receives
left
message, node forwards message to next clockwise
from sender node
▪
traverses internal face clockwise
▪
similar
left-hand-rule
•
geometric routing
assumptions
▪
reliable transmission
▪
asynchronous communication
▪
atomic message sent/receipt
Outline
BeRGeR
Definitions
BeRGeR
Definitions
green face
:
union of faces that lie on
the
s
-
t
line
BeRGeR Definitions
green face
:
union of faces that lie on
the
s
-
t
line
G –
s̅t
:
the graph minus the edges that
intersect the
s
-
t
line
BeRGeR Definitions
green face
:
union of faces that lie on
the
s
-
t
line
G –
s̅t
:
the graph minus the edges that
intersect the
s
-
t
line
d
-blue face
:
union of the faces
adjacent to green face and
d
BeRGeR Definitions
green face
:
union of faces that lie on
the
s
-
t
line
G –
s̅t
:
the graph minus the edges that
intersect the
s
-
t
line
d
-blue face
:
union of the faces
adjacent to green face and
d
core
:
traverses green face either left
or right
R
core
L
core
BeRGeR Definitions
green face
:
union of faces that lie on
the
s
-
t
line
G –
s̅t
:
the graph minus the edges that
intersect the
s
-
t
line
d
-blue face
:
union of the faces
adjacent to green face and
d
core
:
traverses green face either left
or right
d
-thread
:
traverses the union of green
face and
d
-blue face
,
left or right
R
core
L
core
TODO: do you prefer
this font for letters on
the diagram?
It is Old Standard TT, the
closest Google slides has to
LaTeX’s Computer Modern
-
Zaz
Outline
BeRGeR
Operation: Cores
BeRGeR
Operation: Cores
s
originates 2 cores:
•
L core
•
R core
BeRGeR
Operation: Cores
s
originates 2 cores:
•
L core
•
R core
they visit the next node clockwise or
counterclockwise on the current face
R
core
BeRGeR
Operation: Cores
s
originates 2 cores:
•
L core
•
R core
they visit the next node clockwise or
counterclockwise on the current face
excluding nodes that are on the other
side of the
st
-
line
R
core
BeRGeR
Operation: Cores
R
core
s
originates 2 cores:
•
L core
•
R core
they visit the next node clockwise or
counterclockwise on the current face
excluding nodes that are on the other
side of the
st
-
line
BeRGeR
Operation: Cores
R
core
s
originates 2 cores:
•
L core
•
R core
they visit the next node clockwise or
counterclockwise on the current face
excluding nodes that are on the other
side of the
st
-
line
two matching cores arrive at
t
BeRGeR
Operation: Cores
s
originates 2
threads
:
•
c
-thread (left)
•
h
-thread (right)
BeRGeR
Operation: Cores
s
originates 2 threads:
•
c
-thread (left)
•
h
-thread (right)
c
is about to originate the
d
-thread.
H
BeRGeR
Operation: Cores
s
originates 2 threads:
•
c
-thread (left)
•
h
-thread (right)
c
is about to originate the
d
-thread.
d
-thread obeys left-hand rule…
R
core
BeRGeR
Operation: Cores
s
originates 2 threads:
•
c
-thread (left)
•
h
-thread (right)
c
is about to originate the
d
-thread.
d
-thread obeys left-hand rule…
… except that it ignores
d
.
R
core
BeRGeR
Operation: Cores
R
core
s
originates 2 threads:
•
c
-thread (left)
•
h
-thread (right)
c
is about to originate the
d
-thread.
d
-thread obeys left-hand rule…
… except that it ignores
d
.
threads continue to follow left or right
hand rule
BeRGeR
Operation
: Braids
s
originates 2 threads:
•
c
-thread (left)
•
h
-thread (right)
c
is about to originate the
d
-thread.
d
-thread obeys left-hand rule…
… except that it ignores
d
.
threads continue to follow left or right
hand rule
R
core
Outline
Correctness: Lemma 1 & 2
Lemma 1.
A core packet traverses a single face of
G – s̅t
and
a thread skipping node k traverses a single face of
G – s̅t –
{k
}
.
i
n
t
u
i
t
i
o
n
:
s
s
e
n
d
s
l
e
f
t
c
o
r
e
(
L
)
u
s
i
n
g
l
e
f
t
-
h
a
n
d
-
r
u
l
e
,
n
g
r
e
e
n
f
a
c
e
,
e
x
c
l
u
d
e
s
e
d
g
e
s
i
n
t
e
r
e
s
t
i
n
g
s
t
-
l
i
n
e
,
r
i
g
h
t
c
o
r
e
(
R
)
s
i
m
i
l
a
r
d
-thread skips
d
and traverses blue face
Lemma 2.
Left and right core paths are internally node-disjoint.
p
r
o
o
f
b
y
c
o
n
t
r
a
d
i
c
t
i
o
n
•
suppose there is a node
v
on both core paths
•
all paths from
s
to
t
must pass through
v
•
this violates the Triconnectivity Assumption
Correctness: Lemma 3 & 4
Lemma 3 (Core validity).
If the target receives a left core and a right core
carrying messages
mₗ
and
mᵣ
respectively and
mₗ = mᵣ
, then
mₗ = mₛ
p
r
o
o
f
•
Lemma 1
⇒
cores traverse only the green face
•
Lemma 2
⇒
the core paths are node disjoint
•
there is only 1 Byzantine node
•
so the Byzantine node cannot affect both cores
Lemma 4 (Thread validity).
If a thread skips a green node
k
and reaches a correct node, it is not originated by
k
.
p
r
o
o
f
•
If
k
originates a thread that skips
k
, that thread is immediately dropped
•
If
k
originates a core, that core contains
k
in its visited list
ℓ
▪
a
c
o
r
r
e
c
t
n
o
d
e
n
e
v
e
r
o
r
i
g
i
n
a
t
e
s
a
t
h
r
e
a
d
t
h
a
t
s
k
i
p
s
a
n
y
n
o
d
e
i
n
ℓ
Correctness: Lemma 5 & 6
Lemma 5.
The path traversed by a left thread does not contain any node of the
right core path. Similarly, the path traversed by the right thread does not contain
nodes of the left core path.
p
r
o
o
f
b
y
c
o
n
t
r
a
d
i
c
t
i
o
n
•
suppose there is a node
v
on the left
k
-thread path
and the right core path
•
all paths from
s
to
t
must pass through
v
or
k
•
this violates the Triconnectivity Assumption
Lemma 6 (Braid validity).
If the fault is adjacent to the green face and the
target receives a core and a matching braid carrying
m
, then
m = mₛ
.
p
r
o
o
f
•
Lemma 5
⇒
left thread path is disjoint from right core path
•
there is only 1 Byzantine node
•
so the Byzantine node cannot affect both a left thread path and a right core path
Correctness: Liveness & Termination
Lemma 8.
Every packet is forwarded a finite number of times.
i
n
t
u
i
t
i
o
n
T
h
e
a
l
g
o
r
i
t
h
m
w
o
r
k
s
b
y
e
x
c
l
u
d
i
n
g
n
o
d
e
s
f
r
o
m
c
o
n
s
i
d
e
r
a
t
i
o
n
t
h
e
n
r
o
u
t
i
n
g
e
i
t
h
e
r
c
l
o
c
k
w
i
s
e
o
r
c
o
u
n
t
e
r
c
l
o
c
k
w
i
s
e
.
So the packets are guaranteed to eventually arrive back at the
sender. At which point they will be dropped.
Lemma 7 (Liveness).
The target eventually receives either
(i) matching left and right core packets or
(ii) a matching core and a braid.
p
r
o
o
f
•
if the faulty node is not on the green face, then matching cores reach target
•
if the faulty node
is
on the green face, then a matching core and braid reach target
BeRGeR Correctness Proof
Theorem 1.
BeRGeR: Byzantine Robust Geometric Routing algorithm solves
the Reliable Message Delivery Problem with a single Byzantine node in a planar
graph subject to the Triconnectivity Assumption.
p
r
o
o
f
t
o
p
r
o
v
e
t
h
i
s
,
w
e
n
e
e
d
t
o
s
h
o
w
3
t
h
i
n
g
s
:
•
validity — an incorrect message is never delivered
✔
Lemma 3 & 6
•
liveness — the correct message is eventually delivered
✔
Lemma 7
•
termination — the algorithm terminates
✔
Lemma 8
BeRGeR: Debrief
•
BeRGeR: fist algorithm to do Byzantine-robust geometric routing
•
complexity:
O
(|
N
|²)
•
can extend to constant packet size if nodes are stateful
•
future:
▪
evaluate performance
▪
max planar graph connectivity is 5: investigate if can tolerate 2 faults
▪
investigate relaxing the Triconnectivity Assumption
QUESTIONS?
Byzantine-Robust Geometric Routing: Basic
Byzantine-robust routing requires
2
f
+1
connectivity (Dolev)
first thought: find 3 disjoint paths
where
f
is the number of Byzantine faults
D
e
l
i
v
e
r
y
C
o
n
d
i
t
i
o
n
2 disjoint paths arrive at target with the same
message:
∃
i
,
j
:
mᵢ
, =
mⱼ
,
pᵢ
∩
pⱼ
= {s
}
Where p is the set of nodes a message has passed
through.
BeRGeR
Introduction
BeRGeR
Introduction
if it were offline routing,
we could just use the
Ford-Fulkerson algorithm
to find 3 disjoint paths
but online, these paths are
hard to find
Byzantine-Robust Geometric Routing: Basic
second thought: find 3
collectively
disjoint paths
D
e
l
i
v
e
r
y
C
o
n
d
i
t
i
o
n
A number of packets arrive at target with the same
message, such that each node is skipped by at least
one of those packets:
∃
i
,
j
,
k
,... :
mᵢ
, =
mⱼ
=
mₖ
,
pᵢ
∩
pⱼ
∩
pₖ
∩ … = {s
}
Where p is the set of nodes a message has passed
through.
The Triconnectivity Assumption
FACE [BMSU01,DSW02]
traverse face, switch as soon as juncture is found
(cross
sd
-line and change traversal direction)
s
d
a
b
c
e
f
g
h
i
j
k
F
G
H
•
message cost
O
(|
V
|
2
)
•
path stretch ?
GPSR [KK00]
variant: traverse face, switch as soon as juncture is found
(do not cross
sd
-line keep traversal direction)
s
d
a
b
c
e
f
g
h
i
j
k
F
G
H
•
message cost
O
(|
V
|
2
)
•
path stretch ?
OAFR [KWZ03a]
traverse in one direction, if found bounding ellipse,
change direction, if bounded in both directions, double ellipse size
s
d
a
b
c
e
f
g
h
i
j
k
F
G
H
•
message cost: outperforms others on
average
•
path stretch:
O
(
ρ
2
) –
optimal
- where
ρ
is shortest path
bounding ellipse
E
Combination of Greedy and Face Routing
•
guarantees delivery while shortening the path
•
go greedy until local minimum is encountered
•
in local minimum – switch to face routing
•
switch back to greedy if closer to destination than this local minimum
•
adding greedy generates combined geometric algorithms
▪
GFG
[BMSU01,DSW02]
▪
GPSR
[KK00]
▪
GOAFR+
[KWZZ03]
s
d
a
b
c
e
f
g
h
i
j
k
F
G
H
COMPASS [KSU99]
traverse entire face, find furthest adjacent face, switch to it
F
G
H
•
message cost
O
(|
E
|)
•
path stretch ?
Geometric Routing enables routing without overhead, where each node knows its global coordinates and forwards messages based on proximity to the destination. Byzantine Faults pose challenges with arbitrary node behavior, but a Byzantine-Robust Geometric Routing algorithm addresses this in a 3-connected planar graph. The outline covers key terms and operations for correct routing, including unit disk graphs and routing assumptions like the right-hand rule. Explore how these concepts contribute to efficient and fault-tolerant routing strategies.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
BeRGeR: Byzantine-Robust Geometric Routing a Zaz Brown Mikhail Nesterenko Gokarna Sharma E L thread g b c H e d L core F s t m R core h j k p q Rabat, Morocco May 29-31, 2024
Geometric Routing: Routing without Overhead static nodes, each node knows its global coordinates, source knows coords of target little overhead no routing tables: each node only knows coords of neighbors no memory: no info kept at node after message is routed no global knowledge simple approaches flooding expensive greedy routing message carries coords of target each node forwards to neighbor closer to destination problem: local minimum what if no closer neighbor? use face routing on planar graph a E L thread g b c H e d L core F s t m R core h j k p q 2
Geometric Routing with Byzantine Faults problem: Byzantine fault: arbitrary node behavior, hardest to counter, can model either faults or intruders in general, requires 2f+1 connectivity can we find 3 disjoint paths offline? Byzantine node resists topology discovery question: can we do geometric routing with Byzantine fault? a E L thread g b c solution: BeRGeR: Byzantine-Robust Geometric Routing algorithm single Byzantine fault 3-connected planar graph (more details later) H e d L core F s t m R core h j k p q 3
Outline geometric routing concepts BeRGeR terms operation correctness a E L thread g b c H e d L core F s t m R core h j k p q 4
Graph Terms unit disk graph: two vertices are adjacent iff they are within unit distance approximates radio model planar (embedding) graph can be effectively constructed from a unit disk graph source (s), target (t) vertices, st-line coords assumed carried by message face: area where any two points can be connected by a line not intersecting graph edges single infinite external face a E L thread g b c H e d L core F s t m R core h j k p q 5
Routing Terms and Assumptions right-hand-rule: if node receives left message, node forwards message to next clockwise from sender node traverses internal face clockwise similar left-hand-rule geometric routing assumptions reliable transmission asynchronous communication atomic message sent/receipt a E L thread g b c H e d L core F s t m R core h j k p q 6
Outline geometric routing concepts BeRGeR terms operation correctness a E L thread g b c H e d L core F s t m R core h j k p q 7
BeRGeR Definitions a E g b c e d s t m h j k p q 8
BeRGeR Definitions green face: union of faces that lie on the s-t line a E g b c e d F s t m h j k p q 9
BeRGeR Definitions green face: union of faces that lie on the s-t line a E g G s t: the graph minus the edges that intersect the s-t line b c e d F s t m h j k p q 10
BeRGeR Definitions green face: union of faces that lie on the s-t line a E g G s t: the graph minus the edges that intersect the s-t line b c e d d-blue face: union of the faces adjacent to green face and d F s t m h j k p q 11
BeRGeR Definitions green face: union of faces that lie on the s-t line a E g G s t: the graph minus the edges that intersect the s-t line b c e d L core d-blue face: union of the faces adjacent to green face and d F core: traverses green face either left or right s t R core m h j k p q 12
BeRGeR Definitions green face: union of faces that lie on the s-t line a E d thread g G s t: the graph minus the edges that intersect the s-t line b c e L core d d-blue face: union of the faces adjacent to green face and d F core: traverses green face either left or right s t R core m h d-thread: traverses the union of green face and d-blue face, left or right j k p q 13
Outline geometric routing concepts BeRGeR terms operation correctness a E L thread g b c H e d L core F s t m R core h j k p q 14
BeRGeR Operation: Cores a E g b c e d s t m h j k p q 15
BeRGeR Operation: Cores s originates 2 cores: L core R core a E g b c e L core d F s t R core m h j k p q 16
BeRGeR Operation: Cores s originates 2 cores: L core R core a E g b c they visit the next node clockwise or counterclockwise on the current face e L core d F s t R core m h j k p q 17
BeRGeR Operation: Cores s originates 2 cores: L core R core a E g b c they visit the next node clockwise or counterclockwise on the current face e L core d F excluding nodes that are on the other side of the st-line s t R core m h j k p q 18
BeRGeR Operation: Cores s originates 2 cores: L core R core a E g b c they visit the next node clockwise or counterclockwise on the current face e L core d excluding nodes that are on the other side of the st-line F s t R core m h j k p q 19
BeRGeR Operation: Cores s originates 2 cores: L core R core a E g b c they visit the next node clockwise or counterclockwise on the current face e L core d excluding nodes that are on the other side of the st-line F s t R core m h two matching cores arrive at t j k p q 20
BeRGeR Operation: Cores s originates 2 threads: c-thread (left) h-thread (right) a E g b c e L core d F s t R core m h j k p q 21
BeRGeR Operation: Cores s originates 2 threads: c-thread (left) h-thread (right) a E g b H c is about to originate the d-thread. c e L core d F s t R core m h j k p q 22
BeRGeR Operation: Cores s originates 2 threads: c-thread (left) h-thread (right) a E d-thread g b H c is about to originate the d-thread. c e L core d d-thread obeys left-hand rule F s t R core m h j k p q 23
BeRGeR Operation: Cores s originates 2 threads: c-thread (left) h-thread (right) a E d-thread g b H c is about to originate the d-thread. c e L core d d-thread obeys left-hand rule except that it ignores d. F s t R core m h j k p q 24
BeRGeR Operation: Cores s originates 2 threads: c-thread (left) h-thread (right) a E d-thread g b H c is about to originate the d-thread. c e L core d d-thread obeys left-hand rule except that it ignores d. F s t R core m threads continue to follow left or right hand rule h j k p q 25
BeRGeR Operation: Braids s originates 2 threads: c-thread (left) h-thread (right) a E d-thread g b H c is about to originate the d-thread. c e L core d d-thread obeys left-hand rule except that it ignores d. F s t R core m threads continue to follow left or right hand rule h j k p q 26
Outline geometric routing concepts BeRGeR terms operation correctness a E L thread g b c H e d L core F s t m R core h j k p q 27
Correctness: Lemma 1 & 2 a E Lemma 1. A core packet traverses a single face of G s t and a thread skipping node k traverses a single face of G s t { k }. L thread g b c H e d L core intuition: s sends left core (L) using left-hand-rule, n green face, excludes edges interesting st-line, right core (R) similar F s t m R core h d-thread skips d and traverses blue face j k p q Lemma 2. Left and right core paths are internally node-disjoint. proof by contradiction suppose there is a node v on both core paths all paths from s to t must pass through v this violates the Triconnectivity Assumption v s t F 28
Correctness: Lemma 3 & 4 Lemma 3 (Core validity). If the target receives a left core and a right core carrying messages m and m respectively and m = m , then m = m a E proof L thread g b Lemma 1 cores traverse only the green face Lemma 2 the core paths are node disjoint there is only 1 Byzantine node so the Byzantine node cannot affect both cores c H e d L core F s t m R core h j k p Lemma 4 (Thread validity). If a thread skips a green node k and reaches a correct node, it is not originated by k. q proof If k originates a thread that skips k, that thread is immediately dropped If k originates a core, that core contains k in its visited list a correct node never originates a thread that skips any node in 29
Correctness: Lemma 5 & 6 Lemma 5. The path traversed by a left thread does not contain any node of the right core path. Similarly, the path traversed by the right thread does not contain nodes of the left core path. H proof by contradiction suppose there is a node v on the left k-thread path and the right core path all paths from s to t must pass through v or k this violates the Triconnectivity Assumption k v s t F Lemma 6 (Braid validity). If the fault is adjacent to the green face and the target receives a core and a matching braid carrying m, then m = m . proof Lemma 5 left thread path is disjoint from right core path there is only 1 Byzantine node so the Byzantine node cannot affect both a left thread path and a right core path 30
Correctness: Liveness & Termination Lemma 7 (Liveness). The target eventually receives either (i) matching left and right core packets or (ii) a matching core and a braid. proof if the faulty node is not on the green face, then matching cores reach target if the faulty node is on the green face, then a matching core and braid reach target a Lemma 8. Every packet is forwarded a finite number of times. E L thread g b intuition The algorithm works by excluding nodes from consideration then routing either clockwise or counterclockwise. c H e d L core F s t So the packets are guaranteed to eventually arrive back at the sender. At which point they will be dropped. m R core h j k p q 31
BeRGeR Correctness Proof Theorem 1. BeRGeR: Byzantine Robust Geometric Routing algorithm solves the Reliable Message Delivery Problem with a single Byzantine node in a planar graph subject to the Triconnectivity Assumption. proof to prove this, we need to show 3 things: validity an incorrect message is never delivered Lemma 3 & 6 a E liveness the correct message is eventually delivered Lemma 7 L thread g b c H e d L core termination the algorithm terminates Lemma 8 F s t m R core h j k p q 32
BeRGeR: Debrief BeRGeR: fist algorithm to do Byzantine-robust geometric routing complexity: O(|N| ) can extend to constant packet size if nodes are stateful future: evaluate performance max planar graph connectivity is 5: investigate if can tolerate 2 faults investigate relaxing the Triconnectivity Assumption a E L thread g b c H QUESTIONS? e d L core F s t m R core h j k p q 33
