Skip to content

Instantly share code, notes, and snippets.

@jki127

jki127/distsys-dec-4-2018.md Secret

Last active December 18, 2018 00:13
Show Gist options
  • Save jki127/b29894ac073c9799d4ede6eb077dbe8d to your computer and use it in GitHub Desktop.
Save jki127/b29894ac073c9799d4ede6eb077dbe8d to your computer and use it in GitHub Desktop.
Download ZIP
Raw
distsys-dec-4-2018.md

Commander & Lieutenants - DistSys Lecture - Dec 4th, 2018

https://cse.buffalo.edu/~stevko/courses/cse486/spring14/lectures/36-bft1.pdf

Invariant 1

All loyal lieutenants follow the same order even if the commander is a traitor

Invariant 2

If the commander is loyal, every loyal liuetenant obeys his command

Example: 1 Commander and 2 Lieutenants

  • A commander sends all the lieutenants either an attack or retreat message
  • The lieutenants send each other the message that they received from the commander
  • If a lieutenant receives differing messages from the commander and the lieutenant, it retreats

Invariant 2 can’t be supported if one lieutenant is a traitor. The commander can send attack, but the 1 loyal lieutenant will retreat if the unloyal lieutenant tells it to retreat

Oral Messaging Algorithm

  1. Each lieutenant sends each other the message they receive from the commander
  2. Each lieutenant sends other lieutenants the messages they receive from other lieutenants

Build out the OM tree. For every level of depth we go, we remove the effect of one traitor

Number of messages

k = # of lieutenant nodes

1 Level

1 message

2 Levels

1 + k

3 Levels

1 + k + k(k-1)

4 Levels

1 + k + k(k-1) + k(k-1)(k-2)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment