I want to broadcast a message to my friends around the world and I have a couple of requirements
- make sure everyone definitely gets it
- make sure everyone gets it soon
- send as few messages as possible
- it should work for everyone
How might I approach this?
the simplest way would be to make a connection to each friend and send it to them directly. If I have 100 friends, that is 100 messages - that is actually good! but the problem is if everyone wants to distribute messages this way everyone needs 100 connections! to connect everyone to everyone means thousands of connections! This is a lot of work for each computer.
lets say, everyone has just 5 connections to some other random friends, so you send a message to 5 people, they each send it to another 5 (thats 1+25 now) who then send it to another 5 (that is 1+25+125) now everyone has the message and some people have probarly received (since 151 messages went to 100 people) that isn't efficient. but it was less work for my computer! I only needed to send it to 5 people! I'm okay with that!
okay so lets try the above, can we avoid sending it to anyone again? We could do that if we had a thing called a "spanning tree" a spanning tree is a network that connects everything but doesn't have any extra connections. That means there is no loops - there is always a shortest path between any two friends (that may go through other closer friends).
If you think of a ordinary tree it's like this - because all the branches come off the trunk, and then the leaves come off those branches. If you where an ant and wanted to travel from one leaf to another, you'd start walking towards the trunk, then go onto the branch the other leaf came off etc.
An ordinary tree grows in this shape, so it's easy to see what the paths are, but the problem we have is all the leaves are in a jumble and we don't actually know which ones are close to each other!
if we had some sorts of top down view of the network, we could look and see which people where closest to each other, and tell them to connect. The people in far flung places would connect to people in more populous places who would connect to each other and messages would travel along those lines.
But this has a big important job that someone has to do, and who is gonna pay them to do it? We'd rather have a system where everyone can just do their thing without any one having special responsibility (because that isn't fun)
what if there was a way that people could just figure out on their own who is the closest? well, actually there is! When you send someone a message, you can measure how long it takes them to send a message back! this is equivalent to how close you are together! So, lets say we connect to random people like in the 2nd method - but then if we receive another message that we already know, we deactivate that connection. (since if we already know that message, we must have a faster path to the source along another path)
So, the first time we build the network, it will have lots of extra connections, but the ones we don't need will get switched off. If we sometimes add new connections to other random people We'll eventually end up with the best network, the same as the top down network, but without having to have anyone at the top!
So, once the network has "warmed up" it only needs to send 100 messages to make sure everyone gets everything, but no one person needs to send more than a couple of messages.
okay, this story really needs pictures. also glosses over some aspects, but it's the basic gist of it.
By @dominictarr