Zanopia – Stateless application, database & storage architecture

Objects and the cloud.

Automatic ID assignment in a distributed environment

leave a comment »

In the area of distributed computing, unique ID assignment for machines composing a cluster is often required. When the number of machines is huge, these IDs are generally generated automatically and randomly. This works if systems pick really big random numbers (e.g. 128bits), assuming collisions are unlikely.

Occasionally it is required that systems chose ID with a small number of bits (e.g. 1000 machines with a 16 bits ID). In this case the ID assignement scheme cannot rely on randomness but requires a network and computational challenge. It is exposed here:

In ancient China, under the Tang dynasty, Hong WeiAn was an official at court. He was a very talented accountant and his favorite occupation was to submit maths games to his subordinates. One day he brought them all into the imperial garden and asked them the following problem:

"My friends, you are today 100 people. Put you in a circle. You all have to choose a unique number from 0 to 99, but there are some rules…".

Automatic_numbering1
"1 – The first rule is that you can only talk to one person at a time."

"2 – The second rule is that you must not elect a leader".

"3 – There must be the less possible conversations."

And he finished:

"4 – Don't rely too much on randomness! because if you choose a number randomly then the chances for two of you having the same number is nearly 100%"

 

For clarity, in a modern language it would be understood like:

1 – No broadcast

2 – No leader election to make the job.

3 – The goal is to find a converging solution with the less possible messages exchanged between the subordinates.

4 – Beware of the Birthday paradox! The probability of colliding is approximatively 7d0914f413b28b8ecd626b3268240604 , with n~7 and  |E|=100, nearly 100%

Automatic_numbering2
All subordinates have the right to remember which person he has spoken with, they must use the best strategy to converge to the solution without doubt.

Automatic_numbering3
At the court of the Emperor, the subjects were very honest and dedicated, so there is no liars and no failures.

The solution of the problem is the generalization of the algorithm and the protocol for any number of subjects for the less possible number of messages.

Please preferably provide a solution where participants do not exchange lists but simple small packets question/answers.

Please post your solution!

Advertisements

Written by Giorgio Regni

November 15, 2010 at 12:04 pm

Posted in Algorithm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: