What’s the best algorithm to assign unique ID/serial numbers to a group of identical objects?

to make this question easier to visualize, let’s call this the “chicken mesh problem”.

Suppose you have a rooster and a number (suppose it is 30) of baby chickens.

Goal: Allow the rooster to uniquely ID each and single one of the baby chickens,and RELAY messages (indirectly, hence the word “RELAY”) to a specific baby chicken. (For chickens close to the rooster, he can talk directly to them, but that’s beside the point)

Limitations & conditions:

  • The rooster can talk to some (those that are close to him), but cannot ID any of the chicken before assigning IDs to them (let’s just patch that loophole right form the start)
  • The rooster can only access/talk directly to a very limited few chickens close to him, and for chickens far away, he can only pass messages (which may includes ID information or other information, the packets/messages are customizable) to chickens (yes, more than one chickens) near him, and let those chickens relay the messages, using flood method.
  • Any 2 chickens close (I understand “how close” could be a major problem, but for the time being, let’s just define it as “right next to each other”) to each other can talk to each other.
  • The chickens are scattered all over irregularly. Picture a huge chess board beneth them and it has much, much more grids, the chickens radomly occupy these grids, BUT you can always find a way to relay the message from rooster to everyone, even it means a great deal of messages will have to pass one pair of chicken, because these two are close to each other, and they unintentionally forming up some sort of “bridge” between two larg chicken groups.

A walkthrough of what may happen should you try to assign each baby chicken with a unique ID number (just an example, not the actual implementation as I do not know how):

The rooster talks to the chicken closest to him using a configuration packet of some sort, and name the chicken “0x01”, then the rooster talks to another chiken next to him (in reality, this order could be caused by distance, or purely random) and name it “0x02”. Then 0x02 passes this configuration packet to another chicken with a certain flag set informing anyone receiving this packet that ID “0x02” was already taken. This process is repeated until a chiken gets an ID “0x1E”, and from that point on, no one will respond to any configuration packets, and every single chicken can be uniquely ID-ed as it will simply ignore packets which contain IDs different than it’s own.

Note that the above scenario isn’t the actual implementation, just an example to help you understand what’s likely to happen.

Last but not least, please do not get any routing algorithm involved, please use “dumb” flood only. And yes, I know it’s kinda unreasonable, but I have to implement the whole scheme using very low end equipments, low end enough that I do not have the kind of RAM and likely not even the computing power to run an active routing process.

And by flood, please do not worry about the messages being repeated infinitum thus overloading and paralysing the entire network, there already are mechanisms in plaec to prevent that (e.g. reduce the frequency a message get repeated exponetially)

The whole point is, I’m sure there are algorithm for this, but I don’t have a solid background in SE or CS, so please help?


You will want to do some research on low level network protocols – this is a solved problem.

Here’s an outline, based on a networking class I took 20 years ago.

Step 1: Have your rooster send out a message

all chickens who receive this directly: a) I am chicken ID 0x00. b) do not rebroadcast this message, and c) pick a random 32 bit integer and reply to this message with that number

Step 2: Have your rooster reply to each respondent:

To the chicken who sent ‘431151231’: You are now ID 0x01.

To the chicken who sent ‘513413412’: You are now ID 0x02.

If by some miracle two chickens sent the same random number, ask them to generate a new number and resend. Hope they are not using the same random seed.

Step 3: Send a message to each first tier chicken in turn:

Chicken 0x01: send this message to all of your direct connections, and relay the results to me (0x00): all chickens who receive this message, do not rebroadcast it, but reply with a random 32 bit integer.


Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *