Kademlia Iterative Find (v1)

gistfile1.txt

# 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)