[ripple/rippled] Increase validation quorum to 80% (#2613)

mtrippled commented on this pull request.

I also am still studying the white-paper and plan to go through each step of the proof that 80% quorum is sufficient to support as little as 90% validator list overlap.

> }

for (auto const& k : trustedKeys_)
trustedKeys_ = std::move(newTrustedKeys);

My hunch tells me that there is a more efficient way to do this for the normal case. The normal case is where there are no changes to the validator lists. Namely:

for each key in trustedKeys_:
if key not in keyListings_ or key is revoked:

for each key in keyListings_:
res = emplace key in trustedKeys_
if res was already there:

In that case, each list is scanned once for presence of each item in the other list. Also the revocation list is scanned for each item. No changes to any objects are made.

I believe that this would be more efficient than creating a new set, destructing the old, and then inserting and erasing each item into the new and old objects, respectively.

And in the event of a change, such as either through expiration or new/removed entries, just doing the setTrusted() or
setUntrusted() immediately is better than creating a struct of 2 sets to keep track of the changes, to then walk through to feed to setTrusted() and setUntrusted().

If it’s important to log the number of changes, then simple counters can be created and incremented.

And even in a case where there are changes to be made to the validator list, I’m not sure how much would be gained, if anything, performance-wise doing things the way implemented currently in this PR.

This post was last modified on July 6, 2018, 7:41 pm