Iterative deferred

Iterative lookups use the home made iterative deferred pattern to process parralel lookups on the DHT. This pattern aims at abstracting this kind of task in the functionnal programming's map/reduce style.

Somehow, the iterative deferred pattern differs from the tradional map/reduce since the map function, instead of returning directly the result, should return a Deferred which result is the one consumed by the reduce function. An other difference – the one, that makes this process iterative – is the possibility to feed the map function during the process inside the reduce function.

In addtion, the iterative deferred pattern is embodied in a Deferred object that is completed when the process ends. That's why this pattern could be named iterative map/reduce deferred, but that's too long..

IterativeDeferred inherits from Deferred.

Interface

# id.map(mapFn)

Setter for the map function.

The map function to be defined: should map a key to a Deferred object. Return a deferred object that wil be registered: the iterative process won't stop untill all registered deferreds are completed or a manual intervention occurs. If the key has already been mapped, the mapping will be ignored.

# id.init(value)

Set itinial reduce value.

# id.reduce(reduceFn[, initValue])

Setter for the reduce function. One could also set the itinial reduce value with initValue.

The reduce function to be defined: should combine resolved result from mapped deffered and the previous reduce result. It can feed the mapping process with keys to map, by calling the map argument function. If the deffered resolved mutliple arguments, the addtional arguments are present after result.

At any moment the iterative process can be stopped manually just by completing the working process as deferred: simply call this.resolve or this.reject.

The end arguments key, resolved and rejected are here if needed to decide the reduce process.

• previous : previoulsy returned by the reduce function
• result : the result resolved by the mapped Deffered
• map : use this function to feed the mapping process with new keys
• key : original mapping key whose deffered produced the given resolved result
• resolved : array of keys wich mapped Deferred has been resolved
• rejected : array of keys wich mapped Deferred has been rejected

# id.end(endFn)

Setter for the end function.

The final function, will be called when the iterative process ends, ie there is no more uncompleted mapped Deffered and all reduce process are finished. The final function should complete the process by calling this.resolve or this.reject. If this is not done, the process will be automatically resolved.

• reduceResult : what finally came out the reduce process
• resolvedKeys : array of keys wich mapped Deferred has been resolved
• rejectedKeys : array of keys wich mapped Deferred has been rejected

# id.start(keys)

Start the iterative map/reduce given an array of map keys.

Example : crawling a linked list using IterativeDeferred

To understand how IterativeDeferred would be used a linked-list. This example is really simple since the chosen data-structure is but the pattern is adapted to crawl more complex structures like trees, and that's why it is adapted for iterative look-up on a DHT.

Considering this linked-list :

Assuming next hook is retrieved through a Deferred object named GetNext that would react like that :

hook = new GetNext(2);

hook.then(function(result) {
  // result ->
  // { nextKey : 3,
  //   value   : 4
  // }
});

To crawl this linked-list using IterativeDeferred :

var crawl = new IterativeDeferred([1])
                .map(function(key) {
                  //generate a deferred
                  return new GetNext(key);
                })
                .reduce(function(prev, result, map) {
            
                  //we continue with next key as long there is more
                  if(result.nextKey)
                    map(result.nextKey);
            
                  //add found value to our reduce result
                  prev.push(result.value);
            
                  return prev;
                }, [])
                .end(function(reduceRes) {
                  //at the end, we resolve
                  this.resolve(reduceRes.join('->'));
                });
            
crawl.then(function(res) {
  console.log(res)
});

And you should get :

1->4->9->16->25->36->49->64->81->100

If you really want to test this code, you could mock the GetNext like that :

var linked_list = function(key) {
  return {
    value : key*key,
    nextKey  : (key <10) ? (key)+1 : false 
  };
};

var GetNext = Deferred.extend({
  initialize: function(nexKey) {
    this.supr();
    setTimeout(function(that) {
      that.resolve(linked_list(nexKey));
    },200, this)
  }
});

Example : the Chord algorithm

Here is a concrete application of how you could implement the [Chord](http://en.wikipedia.org/wiki/Chord_(peer-to-peer\)) algorithm using this iterative-deferred pattern.

var me = 33;

// returns the closest preceding node from
// the finger table  
function closestPrecedecessor(id) {
  // ...
};

function findSuccessor(id) {
  
  var lookup = new IterativeDeferred();

  function map(successor) {
    var req = FindSuccessorRPC(successor);
    res.send();
    return req;
  }
  
  function reduce(successor, successors, map) {
    successors.unshift(successor);
    if (id <= myId || id > successor) {
      map(closestPrecedecessor(successor));
    }
    return successors;
  }

  return lookup
          .map(map)
          .reduce(reduce, []);
}

findSuccessor(74).then(function(successors) {
  console.log(successors); // all the node found during the process
  console.log(successors[0]); // the node predecessor of 74
});