Alice wants to send a love note to Carl, but she is afraid that the Evil Teacher will steal it and read it out loud. So she comes up with a plan, she'll send Carl the note letter by letter. That way she can stop writing the note if the teacher steps in, to avoid any embarrassment.
Unfortunately, Alice does not have Google Docs to share notes with Carl. So how might she build something like it? As we will see, sending letters one by one won't work. Click next to learn why. Then we will show you how to help Alice solve the problem.
Our previous article on relative ordering explained the algorithms necessary to create apps like chat rooms and news feeds. Most applications are just glorified lists, like a thousand todo apps combined together in different ways. But some use cases require more complex data structures, like a game world, diagramming tools, inventory trackers, etc. and that is where dependent causality comes in. Let's see how it works, click next.
The reason sending letters one by one won't work is because we cannot trust the mail man. Bob sits between Alice and Carl, and while Bob is a loveable guy, he sometimes gets hungry. And what better snack is a glue sandwhich with paper bread?
It does not matter whether you are sending mail via USPS, a homing pidgeon, pony express, or email via the internet with WiFi or LAN. They are all Bob. They are the glue that connects us together, but they will all fail at some point. We cannot trust them as being reliable - if we did, our app may unexpectedly crash.
So how do we overcome this problem? Let's see what Alice does next, click next.
Great! If we give each of our messages a unique ID, we can resend it multiple times until it goes through. If Carl receives the same message more than once, he knows to ignore the duplicate based on the ID. This is the idea behind at least once delivery, which guarantees a message will eventually be successful.
But, oh no! Alice has a new problem. Because she is sending multiple messages out, and occasionally resending them, the letters got out of order. This is a timing error. Take a guess at how we might solve for this, and then click next.
Note, it is possible we could just wait a long period of time between each message. This would decrease the odds of messages getting out of order. However it is not provably guaranteed unless we wait for an acknowledgement on every message before we send the next one. That would work, but it is slow. Ideally, our solution should be fast and guaranteed.
Alice has another idea. What if each message also said what its previous message ID was? That way, even if Carl gets the messages out of order, all he has to do is sort them as they come in. He would also know which message is the first one in the series because it would have no dependency on any other message.
And there you have it! Each message specifies its causality by saying what its previous dependencies are. Now, no matter how many times the network fails or the messages get out of order, Carl is always able to recover the original meaning. And he can do this in realtime as Alice types her message, opening any letters that link back to the start, and simply waiting for ones that have gaps until the links fill in.
Congratulations, that is all it takes! Pretty simple, huh? Even the most complex apps can be built by creating a data structure which precisely describe the dependent causality of its information.
Interestingly enough, Google Docs does not use this approach, however Git does. Google Docs uses an algorithm called Operational Transformation which requires a centralized server to correctly produce the results. While it is possible to build OT with GUN, you would lose all the advantageous of GUN's decentralized graph architecture. Which is why we recommend using an algorithm similar to above, you can check out a prototype of it in action here.
We hope you enjoyed this article. But wait, isn't there one last problem? Yes, nothing stops the Evil Teacher from spying on Alice's conversation with Carl. But we have a way to stop that! Check out our animated explainer series on cryptography next!
