d12 algorithm

[swirlds-automation]

The next step is to implement the d12 algorithm. I strongly suspect it's not actually needed. But both I and Atul were unable to mathematically prove correctness without it.

When calculating the consensus for round R, we do n election for the fame of each judge in R. The election for round R witness X starts with each witness in round R+1 voting yes or no, based on whether it can see X.  That's how the current code works. Actually, we define a constant d=1, and say that its the witnesses of round R+d that have the initial votes based on seeing X.

When the election finishes, and we now know all the judges in R, we would normally go ahead and find all the consensus events in R. But we will change the code to add one extra step here. We will check whether or not the judges in R form a supermajority. In other words, the creators of those judges should together have more than 2/3 of the stake.  I strongly suspect this is mathematically guaranteed to happen. But I and Atul couldn't find a proof. So we need to do the check in the code, just to make sure.

In the unlikely case that we have too few judges, then we should start over and recalculate consensus for round R from scratch, using d=2 this time.  In other words, a witness Z in round R+2 will vote yes for a witness X in round R if and only if there exists some witness Y in round R+1 such that Z sees Y and Y sees X. So this check will involve a FOR loop through every possible Y, which stops as soon as a Y is found that lets Z see X indirectly through that Y. 

There is a mathematical guarantee that d=2 will give us a supermajority of judges. 

So there's no need to even check the second time.So the algorithm in the current code is called the "d1 algorithm" because it uses d=1.  And you'd want to code and test the "d2 algorithm" where d=2, to make sure it works. And then you'd add the IF statement to the code that tries d=1, and if it fails to get enough judges, tries again with d=2.  That's the d12 algorithm.

Of course, ideally we'd test the d12 algorithm by giving it a hashgraph designed to trigger the need for the recalculation. But Atul and I were never able to find such a hashgraph. So we'll have to settle for just testing d1 and d2, and then checking that d12 works, even though we've never seen d12 do the second d2 phase in testing.

That's the d12 algorithm

[swirlds-automation]

_{migrated from: url=https://github.com/swirlds/swirlds-platform/issues/6650 author:lpetrovic05, #:6650, createdAt:2023-02-08T09:59:09Z, updatedAt=2023-02-17T23:00:51Z labels=Migration:Hashgraph}

[poulok]

@lpetrovic05 is this ticket still relevant?

[lpetrovic05]

yes. should I create an epic with outstanding consensus tasks?

[poulok]

yes. should I create an epic with outstanding consensus tasks?

There already is one: https://github.com/hashgraph/hedera-services/issues/5422

I added it.