Skip to content

Instantly share code, notes, and snippets.

@alexstrat
Created January 4, 2012 20:11
Show Gist options
  • Save alexstrat/1561850 to your computer and use it in GitHub Desktop.
Save alexstrat/1561850 to your computer and use it in GitHub Desktop.
Iterative find process for Kademlia (v2)
# 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
Trap <- Array of peers
ALPHA <- 3
K <- 8
fn: start the process
send parallel FIND_NODE to the ALPHA (or less) first closest peers of HeardOf
add these peers to Queried
and handle the response.
fn: fail_handler () -> # timeout, error..
add the requested peer to NotReached
- if there is no more request on the fly (Reached U NotReached U Trap == Queried)
END of process : fail
fn: success_handler (responded peers) ->
add the requested peer to Reached
add the responded peers to HeardOf
- in CASE targeted ID is one of responded peers
END for process : success.
- in CASE there is no more request on the fly
END of process.
- in CASE there is new closest peer in HeardOf
send parallel FIND_NODE to the ALPHA (or less) first peers closest of HeardOf that are :
* not in Reached nor NotReached
* not in Queried
* nor in Trap
add them to Queried and move the other Queried peers to Trap
and handle the response.
- other CASE
send parallel FIND_NODE to the K (or less) first closest peers of HeardOf that are :
* not in Reached nor NotReached
* not in Queried
* nor in Trap
add them to Queried
and handle the response.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment