Created
January 4, 2012 20:11
-
-
Save alexstrat/1561850 to your computer and use it in GitHub Desktop.
Iterative find process for Kademlia (v2)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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