Please pose your solutions to the Feb 2 In-Class Exercise to this thread.

Best,

Chris

If we use the random number generator used in line 3 in the randomly permutating arrays method (Method 1), we can have a scenario where each device can have a unique identifier with probability 1 - 1/n. For n = 4 billion, this comes out to 0.99999999975 which is greater than 0.999999999. 2^96 - 1 is the number of unique identifiers that can be stored in 96 bits. This comes out to be 7.92 * 10^28 which is less than n^3 (n is 4 billion). So our algorithm can generate a unique priority number which can act as the unique identifier.

Since 2^96 ~= 7.9e+28 and 4 billion^3 ~= 6.4e+28, meaning that the possibilities from a 96 bits identifier is larger than the maximum possible sample space of n^3.

Thus, simply accessing the random number generator for a number from 0 - 2^96 -1, it will be an unique identifier with probability greater than 1 - 1/4billion 2^32.

---

So on each device, they can access the random number generator, returning 0 or 1, 96 times, as their 96-bits identifier. They will have probabilities higher than the required one to be unique.

generate_identifier():

	return random(1, 2**96 - 1)

Since we need to identify max 2**32 devices, if we generate random numbers within (2**32)**3, the probability that all the identifiers are unique is at least 1- (1/2**32).

There can be a maximum of 4 billion devices which is 2^32. By using the first method each machine can generate identifiers between 0 to 2^96-1. Hence 2^32 machines generating unique numbers upto 2^96-1 then the probability of this algorithm is 1/1-n which is 1/1-2^32 = 0.99999999975 which satisfies the condition given.

We could directly pick a random value between 0 and 7.9228e+28 - 1 (i.e. 2^96-1) as an identifier for every individual device: as shown in the first randomization method.

Reasoning: The maximum number of possible identifiers is greater than the maximum number of network devices (4e+9), and thus the probability of each identifier being unique would be > (1- 1/(4e+9)) i.e. > 0.99999999975.

We know that n, the number of devices to identify, is less than 4 billion, which is also less than 2^32, an easy number for computers to understand. Given we have up to 96 bits to use, we can generate a random number between 0 and 2^96-1 (96 = 32 * 3), and the probability that the identifiers are unique is 1/1-2^32 = 0.99999999975 > 0.999999999.

Using the random number generator to return 0 or 1, 96 times for a 96-bit identifier, we can satisfy the conditions. The possibilities from a 96 bit identifier is greater than the sample space where n = 4billion. The probability of 1/1-2^32 (first randomization method) is also greater than required probability of 0.999999999.

We will use the first method. Here n is 4 billion. AS per the proof of the first method, Probability( all our unique) > 1 - 1/n 96 bits = (2*32)^3 2^ 32 = 4294967295 > 4 billion. So therefore there are about (2*32)^3 = n^3 , possibilities which is fits well in our algorithm, therefore P(Unique identifiers) > 1-1/4billion

Pick a random number between 1 and n^3, where n < 4,000,000,000. This number identifier will be in any range between 1 and 6.4e+28, which is within the condition of less than 96 bits, that is 2^96 = 7.92e+28.

From the lecture notes, we have proven the claim that the probability that all the priorities are unique is at least 1- 1/n.

So at most, the probability that we will have all unique identifiers will be at least: 1 - 1/4,000,000,000 which is greater than 1 - 1/1,000,000,000.