{
  "name": "k-bucket",
  "version": "0.4.2",
  "description": "Kademlia DHT K-bucket implementation as a binary tree",
  "scripts": {
    "test": "node scripts/test.js"
  },
  "main": "index.js",
  "devDependencies": {
    "nodeunit": "0.9.x"
  },
  "dependencies": {
    "buffer-equal": "0.0.1"
  },
  "repository": {
    "type": "git",
    "url": "git@github.com:tristanls/node-k-bucket.git"
  },
  "keywords": [
    "k-bucket",
    "kademlia",
    "dht"
  ],
  "contributors": [
    {
      "name": "Tristan Slominski",
      "email": "tristan.slominski@gmail.com"
    },
    {
      "name": "Mike de Boer",
      "email": "info@mikedeboer.nl"
    },
    {
      "name": "Conrad Pankoff",
      "email": "deoxxa@fknsrs.biz"
    },
    {
      "name": "Feross Aboukhadijeh",
      "email": "feross@feross.org"
    }
  ],
  "license": "MIT",
  "readme": "# k-bucket\n\n_Stability: 1 - [Experimental](https://github.com/tristanls/stability-index#stability-1---experimental)_\n\n[![NPM version](https://badge.fury.io/js/k-bucket.png)](http://npmjs.org/package/k-bucket)\n\nKademlia DHT K-bucket implementation as a binary tree.\n\n## Contributors\n\n[@tristanls](https://github.com/tristanls), [@mikedeboer](https://github.com/mikedeboer), [@deoxxa](https://github.com/deoxxa), [@feross](https://github.com/feross)\n\n## Installation\n\n    npm install k-bucket\n\n## Tests\n\n    npm test\n\n## Usage\n\n```javascript\nvar KBucket = require('k-bucket');\n\nvar kBucket = new KBucket({\n    localNodeId: new Buffer(\"my node id\") // default: random data\n});\n```\n\n## Overview\n\nA [*Distributed Hash Table (DHT)*](http://en.wikipedia.org/wiki/Distributed_hash_table) is a decentralized distributed system that provides a lookup table similar to a hash table.\n\n*k-bucket* is an implementation of a storage mechanism for keys within a DHT. It stores `contact` objects which represent locations and addresses of nodes in the decentralized distributed system. `contact` objects are typically identified by a SHA-1 hash, however this restriction is lifted in this implementation. Additionally, node ids of different lengths can be compared.\n\nThis Kademlia DHT k-bucket implementation is meant to be as minimal as possible. It assumes that `contact` objects consist only of `id`. It is useful, and necessary, to attach other properties to a `contact`. For example, one may want to attach `ip` and `port` properties, which allow an application to send IP traffic to the `contact`. However, this information is extraneous and irrelevant to the operation of a k-bucket.\n\n### arbiter function\n\nThis *k-bucket* implementation implements a conflict resolution mechanism using an `arbiter` function. The purpose of the `arbiter` is to choose between two `contact` objects with the same `id` but perhaps different properties and determine which one should be stored.  As the `arbiter` function returns the actual object to be stored, it does not need to make an either/or choice, but instead could perform some sort of operation and return the result as a new object that would then be stored. See [kBucket.update(contact, index)](#kbucketupdatecontact-index) for detailed semantics of which `contact` (`incumbent` or `candidate`) is selected.\n\nFor example, an `arbiter` function implementing a `vectorClock` mechanism would look something like:\n\n```javascript\n// contact example\nvar contact = {\n    id: new Buffer('contactId'),\n    vectorClock: 0\n};\n\nfunction arbiter(incumbent, candidate) {\n    if (incumbent.vectorClock > candidate.vectorClock) {\n        return incumbent;\n    }\n    return candidate;\n};\n```\n\nAlternatively, consider an arbiter that implements a Grow-Only-Set CRDT mechanism:\n\n```javascript\n// contact example\nvar contact = {\n    id: new Buffer('workerService'),\n    workerNodes: {\n        '17asdaf7effa2': { host: '127.0.0.1', port: 1337 },\n        '17djsyqeryasu': { host: '127.0.0.1', port: 1338 }\n    }\n};\n\nfunction arbiter(incumbent, candidate) {\n    // we create a new object so that our selection is guaranteed to replace\n    // the incumbent\n    var merged = {\n        id: incumbent.id, // incumbent.id === candidate.id within an arbiter\n        workerNodes: incumbent.workerNodes\n    };\n\n    Object.keys(candidate.workerNodes).forEach(function (workerNodeId) {\n        merged.workerNodes[workerNodeId] = candidate.workerNodes[workerNodeId];\n    });\n\n    return merged;\n}\n```\n\nNotice that in the above case, the Grow-Only-Set assumes that each worker node has a globally unique id.\n\n## Documentation\n\n### KBucket\n\nImplementation of a Kademlia DHT k-bucket used for storing contact (peer node) information.\n\nFor a step by step example of k-bucket operation you may find the following slideshow useful: [Distribute All The Things](https://docs.google.com/presentation/d/11qGZlPWu6vEAhA7p3qsQaQtWH7KofEC9dMeBFZ1gYeA/edit#slide=id.g1718cc2bc_0661).\n\nKBucket starts off as a single k-bucket with capacity of _k_. As contacts are added, once the _k+1_ contact is added, the k-bucket is split into two k-buckets. The split happens according to the first bit of the contact node id. The k-bucket that would contain the local node id is the \"near\" k-bucket, and the other one is the \"far\" k-bucket. The \"far\" k-bucket is marked as _don't split_ in order to prevent further splitting. The contact nodes that existed are then redistributed along the two new k-buckets and the old k-bucket becomes an inner node within a tree data structure.\n\nAs even more contacts are added to the \"near\" k-bucket, the \"near\" k-bucket will split again as it becomes full. However, this time it is split along the second bit of the contact node id. Again, the two newly created k-buckets are marked \"near\" and \"far\" and the \"far\" k-bucket is marked as _don't split_. Again, the contact nodes that existed in the old bucket are redistributed. This continues as long as nodes are being added to the \"near\" k-bucket, until the number of splits reaches the length of the local node id.\n\nAs more contacts are added to the \"far\" k-bucket and it reaches its capacity, it does not split. Instead, the k-bucket emits a \"ping\" event (register a listener: `kBucket.on('ping', function (oldContacts, newContact) {...});` and includes an array of old contact nodes that it hasn't heard from in a while and requires you to confirm that those contact nodes still respond (literally respond to a PING RPC). If an old contact node still responds, it should be re-added (`kBucket.add(oldContact)`) back to the k-bucket. This puts the old contact on the \"recently heard from\" end of the list of nodes in the k-bucket. If the old contact does not respond, it should be removed (`kBucket.remove(oldContact)`) and the new contact being added now has room to be stored (`kBucket.add(newContact)`).\n\n**Public API**\n  * [KBucket.distance(firstId, secondId)](#kbucketdistancefirstid-secondid)\n  * [new KBucket(options)](#new-kbucketoptions)\n  * [kBucket.add(contact, \\[bitIndex\\])](#kbucketaddcontact-bitindex)\n  * [kBucket.closest(contact, n, \\[bitIndex\\])](#kbucketclosestcontact-n-bitindex)\n  * [kBucket.count()](#kbucketcount)\n  * [kBucket.get(id, \\[bitIndex\\])](#kbucketgetid-bitindex)\n  * [kBucket.remove(contact, \\[bitIndex\\])](#kbucketremovecontact-bitindex)\n  * [kBucket.toArray()](#kbuckettoarray)\n  * [Event 'ping'](#event-ping)\n\n#### KBucket.distance(firstId, secondId)\n\n  * `firstId`: _Buffer_ Buffer containing first id.\n  * `secondId`: _Buffer_ Buffer containing second id.\n  * Return: _Integer_ The XOR distance between `firstId` and `secondId`.\n\nFinds the XOR distance between firstId and secondId.\n\n#### new KBucket(options)\n\n  * `options`:\n    * `arbiter`: _Function_ _(Default: vectorClock arbiter)_ `function (incumbent, candidate) { return contact; }` An optional `arbiter` function that givent two `contact` objects with the same `id` returns the desired object to be used for updating the k-bucket. For more details, see [arbiter function](#arbiter-function).\n    * `localNodeId`: _String (base64)_ or _Buffer_ An optional String or a Buffer representing the local node id. If not provided, a local node id will be created via `crypto.randomBytes(20)`. If a String is provided, it will be assumed to be base64 encoded and will be converted into a Buffer.\n    * `numberOfNodesPerKBucket`: _Integer_ _(Default: 20)_ The number of nodes that a k-bucket can contain before being full or split.\n    * `numberOfNodesToPing`: _Integer_ _(Default: 3)_ The number of nodes to ping when a bucket that should not be split becomes full. KBucket will emit a `ping` event that contains `numberOfNodesToPing` nodes that have not been contacted the longest.\n    * `root`: _Object_ _**CAUTION: reserved for internal use**_ Provides a reference to the root of the tree data structure as the k-bucket splits when new contacts are added.\n\nCreates a new KBucket.\n\n#### kBucket.add(contact, [bitIndex])\n\n  * `contact`: _Object_ The contact object to add.\n    * `id`: _Buffer_ Contact node id.\n    * Any satellite data that is part of the `contact` object will not be altered, only `id` is used.\n  * `bitIndex`: _Integer_ _(Default: 0)_ _**CAUTION: reserved for internal use**_ The bit index to which bit to check in the `id` Buffer.\n  * Return: _Object_ The k-bucket itself.\n\nAdds a `contact` to the k-bucket.\n\n#### kBucket.closest(contact, n, [bitIndex])\n\n  * `contact`: _Object_ The contact object to find closest contacts to.\n    * `id`: _Buffer_ Contact node id.\n    * Any satellite data that is part of the `contact` object will not be altered, only `id` is used.\n  * `n`: _Integer_ The maximum number of closest contacts to return.\n  * `bitIndex`: _Integer_ _(Default: 0)_ _**CAUTION: reserved for internal use**_  The bit index to which bit to check in the `id` Buffer.\n  * Return: _Array_ Maximum of `n` closest contacts to the `contact`.\n\nGet the `n` closest contacts to the provided `contact`. \"Closest\" here means: closest according to the XOR metric of the `contact` node id.\n\n#### kBucket.count()\n\n  * Return: _Number_ The number of contacts held in the tree\n\nCounts the total number of contacts in the tree.\n\n#### kBucket.determineBucket(id, [bitIndex])\n\n_**CAUTION: reserved for internal use**_\n\n  * `id`: _Buffer_ Id to compare `localNodeId` with.\n  * `bitIndex`: _Integer_ _(Default: 0)_  The bit index to which bit to check in the `id` Buffer.\n  * Return: _Integer_ -1 if `id` at `bitIndex` is 0, 1 otherwise.\n\nDetermines whether the `id` at the `bitIndex` is 0 or 1. If 0, returns -1, else 1.\n\n#### kBucket.get(id, [bitIndex])\n\n  * `id`: _Buffer_ The ID of the `contact` to fetch\n  * `bitIndex`: _Integer_ _(Default: 0)_ _**CAUTION: reserved for internal use**_  The bit index to which bit to check in the `id` Buffer.\n  * Return: _Object_ The `contact` if available, otherwise null\n\nRetrieves the `contact`.\n\n#### kBucket.indexOf(contact)\n\n_**CAUTION: reserved for internal use**_\n\n  * `contact`: _Object_ The contact object.\n    * `id`: _Buffer_ Contact node id.\n    * Any satellite data that is part of the `contact` object will not be altered, only `id` is used.\n  * Return: _Integer_ Index of `contact` if it exists, -1 otherwise.\n\nReturns the index of the `contact` if it exists, returns -1 otherwise.\n\n_NOTE: `kBucket.indexOf(contact)` does not use `arbiter` in the comparison.\n\n#### kBucket.remove(contact, [bitIndex])\n\n  * `contact`: _Object_ The contact object to remove.\n    * `id`: _Buffer_ contact node id.\n    * Any satellite data can be part of the `contact` object, only `id` is used\n  * `bitIndex`: _Integer_ _(Default: 0)_ _**CAUTION: reserved for internal use**_  The bit index to which bit to check in the `id` Buffer.\n  * Return: _Object_ The k-bucket itself.\n\nRemoves the `contact`.\n\n#### kBucket.splitAndAdd(contact, [bitIndex])\n\n_**CAUTION: reserved for internal use**_\n\n  * `contact`: _Object_ The contact object to add.\n    * `id`: _Buffer_ Contact node id.\n    * Any satellite data that is part of the `contact` object will not be altered, only `id` is used.\n  * `bitIndex`: _Integer_ _(Default: 0)_ The bit index to which bit to check in the `id` Buffer.\n  * Return: _Object_ The k-bucket itself.\n\nSplits the bucket, redistributes contacts to the new buckets, and marks the bucket that was split as an inner node of the binary tree of buckets by setting `self.bucket = undefined`. Also, marks the \"far away\" bucket as `dontSplit`.\n\n#### kBucket.toArray()\n\n  * Return: _Array_ All of the contacts in the tree, as an array\n\nTraverses the tree, putting all the contacts into one array.\n\n#### kBucket.update(contact, index)\n\n_**CAUTION: reserved for internal use**_\n\n  * `contact`: _Object_ The contact object to update.\n    * `id`: _Buffer_ Contact node id\n    * Any satellite data that is part of the `contact` object will not be altered, only `id` is used.\n  * `index`: _Integer_ The index in the bucket where contact exists (index has already been computed in previous calculation).\n\nUpdates the `contact` by using the `arbiter` function to compare the incumbent and the candidate. If `arbiter` function selects the old `contact` but the candidate is some new `contact`, then the new `contact` is abandoned. If `arbiter` function selects the old `contact` and the candidate is that same old `contact`, the `contact` is marked as most recently contacted (by being moved to the right/end of the bucket array). If `arbiter` function selects the new `contact`, the old `contact` is removed and the new `contact` is marked as most recently contacted.\n\n#### Event: 'ping'\n\n  * `oldContacts`: _Array_ The array of contacts to ping.\n  * `newContact`: _Object_ The new contact to be added if one of old contacts does not respond.\n\nEmitted every time a contact is added that would exceed the capacity of a _don't split_ k-bucket it belongs to.\n\n## Sources\n\nThe implementation has been sourced from:\n\n  - [A formal specification of the Kademlia distributed hash table](http://maude.sip.ucm.es/kademlia/files/pita_kademlia.pdf)\n  - [Distributed Hash Tables (part 2)](http://offthelip.org/?p=157)\n",
  "readmeFilename": "README.md",
  "bugs": {
    "url": "https://github.com/tristanls/node-k-bucket/issues"
  },
  "homepage": "https://github.com/tristanls/node-k-bucket",
  "_id": "k-bucket@0.4.2",
  "_shasum": "150ab92307e9ec818a9c4e39a5f930eb3aaaa23a",
  "_from": "k-bucket@^0.4.2",
  "_resolved": "https://registry.npmjs.org/k-bucket/-/k-bucket-0.4.2.tgz"
}
