-3

Let's say I want to design a distributed system whose only purpose is to assign each running node a unique identifier in some small range (Say, 5-100 nodes into a 10 bit identifier). When a node is added, it should get an unused identifier. We need to support more than 1024 nodes being added then removed, so of course there needs to be some system for releasing identifiers.

From first principles, what techniques would be used to implement a system like this? How would new nodes be added to the system and learn about the others? How could identifiers be released when a node crashes while guaranteeing that no two running nodes have the same identifier? Is it possible to make a system like this fault tolerant?

Is there some method by which I could test ideas I have to see if they actually work in the presence of failure etc?

Gavin Wahl
  • 103
  • Could you prefix an ID (generated repeatedly on each node and unique to this node only) by node-identifier (fixed/node)? I am not sure why you release node IDs? GUID for example would be unique per machine/node. – NoChance Nov 20 '18 at 11:25
  • The identifiers must fit in 10 bits. The point of this question is learn the techniques needed to solve the problem as specified, not come up with a workaround. – Gavin Wahl Nov 20 '18 at 18:56

1 Answers1

1

The simplest approach would be to assign IDs using an external registry (similar to a DHCP server assigning IPs in a network). Failing that, let a leader node assign IDs. Consensus algorithms for selecting one leader of the cluster exists, and these methods may also be able to handle failure of the leader (with some constraints).

If a leader-based approach is not viable, you may be able to negotiate ID assignments in a peer to peer fashion, especially if the nodes are guaranteed to cooperate (no malicious assignments). Assignment changes slowly propagate through the cluster as nodes update their assignment table from their peers, but this also means that achieving majority confirmation of an assignment may take a while. To create a new assignment, a new node would select an available ID at random and propose this change. Three outcomes are possible: the majority of nodes confirms this assignment, or there is a conflicting assignment in which case a new ID must be tried, or the cluster fails to confirm the assignment before some deadline (e.g. due to network failure).

If cooperation cannot be ensured, the method of last resort would be achieving consensus by recording ID assignments on a private blockchain, possibly using some proof of stake method.

Note that in nearly all of these cases, it would be much simpler to use GUIDs rather than recycling 10-bit IDs.

amon
  • 134,135