Skip to content

Instantly share code, notes, and snippets.

@jki127

jki127/distsys-nov-29-2018.md Secret

Created November 30, 2018 00:18
Show Gist options
  • Save jki127/f1548b33948f5b0dc115b8a80ee84ece to your computer and use it in GitHub Desktop.
Save jki127/f1548b33948f5b0dc115b8a80ee84ece to your computer and use it in GitHub Desktop.
Download ZIP
Raw
distsys-nov-29-2018.md

Hashtables (cont.) & Byzantine Fault Tolerance - DistSys Lecture - Nov 29th, 2018

Keyspace Partitioning (cont.)

Let’s represent this Distributed Hashtable using a circular doubly-linked list

  • Each node knows the node before it and after it.

Removing a Node

Place all the data on the node being deleted on the next node (going clockwise)

Searching for a value

  • Use a fingertable to find the node that has the key you’re looking for

Fingertable

  • A hashtable on each node storing the address to a couple of nodes in the cluster

Byzantine Fault Tolerance

Paxos acceptor with bad value

  • A hacked acceptor might be giving evil values (ex: spoofing)
  • A bug might be causing bad values
  • This is an arbitrary/byzantine failure

Commander & Liuetenants

  1. All loyal lieutenants follow the same order even if commander is a traitor
  2. If the commander is loyal, every loyal liuetenant obeys his command https://cse.buffalo.edu/~stevko/courses/cse486/spring14/lectures/36-bft1.pdf
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment