Multicasting on ephemeral groups in large clusters
The King of a small country invites the entire city to his annual party - 500,000, diverse men, women, & children. As a tradition, each citizen brings the King a bottle of wine. Soon after, the Queen discovers that one of the citizens is trying to assassinate the King by giving him a bottle of poisoned wine. Unfortunately, they do not know which citizen, nor which bottle of wine is poisoned. The poison is completely indiscernible. However, the King has 24 prisoners he plans to execute. He decides to use them as taste testers to determine which bottle of wine contains the poison. The poison when taken has no effect on the prisoner until exactly 24 hours later when the infected prisoner suddenly dies. The King needs to determine which bottle of wine is poisoned by tomorrow so that the festivities can continue as planned. Hence he only has time for one round of testing. How can the King administer the wine to the prisoners to ensure that 24 hours from now he is guaranteed to have found the poisoned wine bottle?
Of course, the answer is to apply binary numbers - assign each prisoner a bit in the vector [0, 0, 0, 0, 0, 0, 0, ...], assign each bottle a number from 0 -> 499,999, & then walk through bottle by bottle having each prisoner sip the corresponding binary number. In 24 hours, the combination of prisoners dead yields the bottle number poisoned.
In a similar fashion, a cluster of 100,000 machines has a combinatorial explosion of nCk possible multicasting addresses. To deduplicate data flow to N towers, I'm curious whether one can multicast/listen to arbitrary groups on a single address with the following (or similar) approach.
Take a clutser of 100,000 towers [0, 0, 0, 0, 0, ...], assign each tower a single bit in the vector, disseminated over the network through a gossip protocol. When the network desires to multicast to a set of N nodes, send a single data stream to the address corresponding to the combination of N. Routers do not listen on a classical ipv6 address for the multicast, but rather check in the destination header if their unique bit exists.
We're currently trying to deduplicate CPU socket writes in a computer vision / broadcast network. This would weaponize bandwidth to shrink the # of redundant writes.
Thanks!
1 comment
[ 4.3 ms ] story [ 13.5 ms ] thread