Negative Space Algorithms

November 23, 2017

Recently, I was reading the paper on the hashgraph consensus algorithm, and was wondering if there was any terminology regarding the class of algorithms that utilized inference in a way similar to the "gossip about gossip" algorithm described in the paper (I haven't fully finished reading or understanding how the "gossip about gossip" protocol works, so this explanation might not fully apply). I'm sure there are plenty of good analogies for algorithms that utilize inference to arrive at a solution to a problem, but for me, seeing the algorithm as something that utilized "negative space" was particularly helpful.

The paper explains that one of the main reasons why the hashgraph algorithm is so fast, is because it does not need to broadcast voting information from each member, gossip, but each member can instead derive voting information from "gossip about gossip". The paper defines this method for computing votes as virtual voting:

Virtual voting - every member has a copy of the hashgraph, so Alice can calculate what vote Bob would have sent her, if they had been running a traditional Byzantine agreement protocol that involved sending votes. So Bob doesn’t need to actually her the vote. Every member can reach Byzantine agreement on any number of decisions, without a single vote ever being sent. The hashgraph alone is sufficient. So zero bandwidth is used, beyond simply gossiping the hashgraph. 1

Virtual voting ends up being a lot more efficient than sending over everyone's votes in terms of network overhead. While the following explanation is one that I didn't fully understand, it sounds like some of the information can be bundled together, and compressed very efficiently -- more efficiently than sending over the raw voting information:

This power comes with very little communication overhead. If a community is simply gossiping signed transactions that they create, there is a certain amount of bandwidth required. If they instead gossip a hashgraph, and if there are enough transactions that a typical event contains at least one transaction, then the overhead is minimal. Instead of Alice signing a transaction she creates, she will sign the event she creates to contain that transaction. Either way, she is only sending one signature. And either way, she must send the transaction itself. The only extra overhead is that she must send the two hashes. But even that can be greatly compressed. 2

If the algorithm works as described, it is not only compressing raw data, but it is also compressing information! Each member can figure out the history of the hashgraph WITHOUT actually being told the history of the hashgraph:

If Alice and Bob both have the same hashgraph, then they can calculate a total order on the events according to any deterministic function of that hashgraph, and they will both get the same answer. Therefore, consensus is achieved, even without sending vote messages. 3

This is where the analogy to negative space comes into play. Negative space can also be considered a "compression algorithm". Consider the situation where I give you a square piece of paper, and asked you to draw a donut shape, where the edge of the donut had to touch the edge of the square paper.

We might start out like this:

Donut Filled Out

So, how much of the canvas did we end up filling up with this method?

Consider the following measurements:

Donut Measurements

Area of Square

By drawing the donut, we ended up filling up around 212058 pixels of the pixels on the canvas. What might this look like if we just filled up the negative space instead? We would still arrive at the same diagram, but maybe we could fill up less space.

Donut Negative Space Area of Negative Space

Wow! So by using negative space, we ended up only filling out around 147943 pixels as opposed to 212058 pixels, which represents 70% of what we had initially filled up. We arrived at roughly the same diagram, but by doing a fraction of the work. Note, that depending on the shape of the donut, you might not always draw less by using negative space!

What other algorithms can we apply negative space to in order to compress data or information? Are there any other algorithms that you can think of that also utilize this method? I couldn't think of any off the top of my head, but let me know if you can think of any!

  1. Baird, Leemon. “The Swirlds Hashgraph Consensus Algorithm: Fair, Fast, Byznatine Fault Tolerance.”, 4. 

  2. Baird, 6. 

  3. Baird, 7.