Milestone 1

Kademlia peer-to-peer systems can be characterised by (α, B, k), where

α: the degree of parallelism, while searching
B: the size of the ID space [0, 2^B-1], as well as the number of buckets
k: the maximum number of nodes allowed in a bucket

Over the course of this and the following milestones, you will implement the basic Kademlia system. Note that for our purposes B = 160 is completely overkill There is no need to abandon SHA1 (or SHA256) as the method of ID generation — generate a hash, extract as many hex digits as desired, and convert that to an integer ID., and I would suggest you set B ∈ [8,16] for a far more manageable ID space. Likewise, α and k can be initially set to small values. As long as (α, B, k) are adjustable, you can later scale your system up according to your requirements.

The first Kademlia operations will be FIND_NODE and PING, so that Kademlia peers can locate each other and thus populate their k-buckets. You must reformulate these operations into something RESTful.

Milestone demonstration

You should be able to launch a number of peers, have them discover each other, and show how their k-buckets are populated. If you wish to demonstrate on your Raspberry Pi, I have monitor/keyboard/mouse/network/power available.

Requirements

All communication between peers should be RESTful. The individual peer should to a Web browserAny HTTP request header features an Accept field, which enables you as developer to ensure that the same request returns, e.g., JSON (when called by a program) or HTML (when called by a browser). Supporting both eases debugging considerably. present a simple page, where the peer’s state (such as id and contents of buckets (the latter ideally presented with links to the respective peers)) can be inspected, and where actions, such as searching for an id, can be performed.

See RESTful Best Practices for a guide on how to formulate an API in accordance with the REST principles. This goes for converting the Kademlia API into nouns (in the URL) and verbs (the method, e.g., GET or POST). One example could be

GET /api/kademlia/nodes/:id

to retrieve the k closest nodes to :id.

You must document your REST API, and bring it to the milestone meeting.

You may assume that one Kademlia peer is initially known and available for bootstrapping and discovery purposes.

Elaboration

There is no centralised component in the system — the initial Kademlia peer is not different in any way from the others, it is merely the first to be launched. Similarly, communication between Web browser and peer takes place directly and not through any central Web server. All peers act as small Web servers.

Hints

You should make the port of a peer configurable, so that you can run many peers on the same machine. This facilitates debugging, and enables you to launch many peers quickly through a script.

Note that the Kademlia specification (p. 6) requires that all RPC calls must have a 160-bit random RPC ID to be echoed in responses. This should be added as a header to the requests and replies. It would also be a good idea to put the source node's ID and port number in headers.

RESTful interfaces can be debugged through browser tools such as Postman or command line tools such as curl, or through extensions to IDEs such as Visual Studio Code.

Debugging distributed systems can be frustrating — it can be eased somewhat by logging all requests and replies with timestamps, so that you can trace what went wrong. Remember that you cannot assume synchronised clocks across machines.