Skip to content

Instantly share code, notes, and snippets.

@jinroh
Last active September 29, 2015 05:57
Show Gist options
  • Save jinroh/1555907 to your computer and use it in GitHub Desktop.
Save jinroh/1555907 to your computer and use it in GitHub Desktop.
Kademlia Iterative Find (v1)
# in this algorithm, all notions of *sorting*, *close* or *distance*
# are relative to the XOR distance with the target ID
# as defined in the Kademlia spec
- iterative find (target ID) ->
# INITIALIZATIONS
HeardOf <- XOR Sorted Array of peers
initialized with the 50 (or less) closest peers we know from the our routing table
Reached <- XOR Sorted Array of peers
Queried <- Array of peers
NotReached <- Array of peers
ALPHA <- 3
K <- 8
(i) start a new process
send parallel FIND_NODE to the ALPHA (or less) first peers of HeardOf which are not in Queried
add these peers to Queried
(ii) stale protection
send parallel FIND_NODE to the K (or less) first peers of HeardOf which are not in Queried
add these peers to Queried
# START
start with (i) and wait for responses
# RESPONSE HANDLER
- handler (responded peers) ->
- if the response is an error (timeout or failure)
add the requested peer to NotReached
- if there is no more request on the fly
- if HeardOf == Queried
stop the process
the process has failed
- else
start the stale protection (ii)
- else
add the requested peer to Reached
add the responded peers to HeardOf
- if there is no new closest peer in HeardOf
- if we accumulated more than K peers in Reached
stop the process
the process has succeeded
- else if there is no more request on the fly
start the stale protection (ii)
- else
restart a new process (i)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment