Election scheduler and prioritization revamp

Yea I guess a bounded frequency would work.

Definitely worth a compare/contrast on them. I didn’t think of LFU, LRU was my gut instinct.

2 Likes

Several questions around the queues within each tier.
Note that all these concerns are alleviated if each block is not inserted into a tier until its previous is confirmed.

  1. Would sorting of the remaining transactions in a tier have to be done every time a transaction is confirmed, due to the possibility of multiple blocks for the same account being present in a queue? This would require n * log(n) time, which seems like it would hamper CPS when queues grow large. Though I suppose a full sort isn't necessary, as you can simply place the affected accounts at the end of the queue. Still, there would be a search, insert, and removal
  2. How would multiple checked transactions from a single account be placed into queues? As in, I send two transactions, A and B, at once. I assume they could be inserted into the priority queue with log(n) efficiency. But what would happen to B once A is confirmed? Would it be put back at the end of the queue?
  3. What if A were to lower my account balance such that B were placed into a lower tier. If B reached the front of its queue first, what would be done with it?
1 Like

Yea that’s worth looking at. Solving that in a decentralized way, maybe it’s as easy as a PR configurable de-prioritization cutoff that goes to the idle queue.

1 Like

I assume this "round-robin" is not a truly random (or sequential loop) of all 128 tiers? Does the long term average have it selecting higher tiers proportional to account balance values (i.e. tiers with 20+ leading zeros are selected FAR less often than tiers with 10+ leading zeros)?

Elsewhere there is a mention of a tier being full and dropping the most recently used account's block. Does this get dropper completely or just to a lower balance tier?

1 Like

On the rebalancing I think we could do a check and recheck before taking an action. I.e. recheck before actually scheduling to see if the account has a new transaction. Or before dropping a transaction if the tier of full.

It could possible be allowed to expand to 2x occupancy and re-checks everything and drops the newest time stamps.

I think the re-check before scheduling is likely needed otherwise we need to scan interdependencies when scheduling.

Yea this container will need to be very fast since it’s close to the network connection.

2 Likes

The round robin part is just iterating buckets 0-127 then starting over so the index of the bucket it’s looking at isn’t random, it picks up where it left off last scheduling decision.

The drop would be completely from the node, requiring the originator to rebroadcast if their priority was so low it wasn’t scheduled on any node.

Idle tier is another option but since every balance possibility is covered by a bucket, this conceptually seems like it could be removed.

Alright so this proposal limits the congestion to it's own tier rather than the whole network which is much better than what we have right now.

How does it deal with the current spam strategy of splitting amount to X amounts then send those X amounts to new accounts and repeat the process for each account. Since every account is new (only have 1 receive and 2 or very few sends). I assume this won't help legit transactions much in the same tier but it will allow other higher tiers to be unaffected, am I correct in my understanding?

2 Likes

Is bucket/tier determined by account balance, or by transaction amount?

1 Like

Tier is determined by account balance. There are 128 tiers. Elections begin at 2^127 to 2^128-1, where, if there are any transactions from an account of sufficient balance, then one transaction is put forward for election. The next election is for 2^126 to 2^127-1, then the next is for 2^125 to 2^126-1, and so on. Then the elections cycle again.

If it looks at each tier in order this seems like a problem. By my count all balances between 1 and 83,000 Nano (roughly) would be grouped into only 17 tiers. Meanwhile 90 of the 128 tiers would have an account value of less than $0.01 USD (currently).

73 tiers correspond to account balances that would have a value of less than $0.01 USD even if Nano had a $100 trillion market cap. Should these even be considered?

Am I missing something?

3 Likes

This was already addressed, see response from @clemahieu here to my similar question

Please let's all read the comments before repeating what's already been said.

1 Like

The balance split method only really benefits the attacker from the single-account confirmation latency. If latency for a single account was zero, it wouldn't matter whether they split it in a tree or do it linearly.

To occupy the bottom tiers they just need enough accounts to fill the occupancy of each bucket, a constant number. Splitting in a tree doesn't provide an advantage over splitting in one bucket, then the next lowest e.g. 100 -> 2 98 -> 2 2 96 -> 2 2 2 94 -> 2 2 2 1 93 -> 2 2 2 1 1 92 -> 2 2 2 1 1 1 91 -> 2 2 2 1 1 1 1 90.

2 Likes

I'm thinking by balance, mostly because it's already in the raw block for other reasons. It will likely need to compare 3 things, source balance, old balance, new balance for cases like initial funding of account or emptying it. If we have those 3 things we'd know the amount anyway, they could be mixed maybe.

It would seem to make sense to weight the selection process towards more commonly used buckets. Perhaps instead of a constant weighting of each bucket, a polynomial minus an exponential would make more efficient use of network resources? Or more likely a lookup table that roughly follows that sort of shape.

Edit: The displayed function is f(x) = (x/8)^2 - 2^(x/16) + 2

2 Likes

Yea I could see an advantage to this. This would be in place of round robin then right? Would a simple pyramid style biasing be enough? That would be the easiest to implement.

8-bucket ordering example:
5, 6 - 4, 5, 6, 7 - 3, 4, 5, 6, 7

1 Like

How are timestamps validated? If those are used as the recently used indicator what’s to prevent someone from sending old/future timestamps to game it for future blocks they intend to send?

What stops someone from changing someone else’s timestamp and what impact would that have on prioritization in the queue?

How are timestamps impacted by nodes bootstrapping old blocks, or a block that gets stuck in the queue for a period of time and later republished to other nodes?

The time stamps aren’t communicated, it’s a node-local timestamp of last account modification. It won’t be precise across the network though I can’t see a need for them to be since there is no penalty to the account owner for an incorrect timestamp.

Signed timestamps would make this part uniform which is nicer but also requires block changes.

So prioritization could be very disjointed if some nodes have to bootstrap blocks and generate different local timestamps?

I’ve seen discrepancies of hours to days between different explorers for the same blocks this past week. While pre-v21.3 isn’t a good example with the syncing issues it seems like everyone should be seeing the same timestamp to be able to prioritize blocks in the same way or could lead to a deadlock where nodes have different active elections.

Especially considering final votes need synchronization between PR’s in order to generate final votes.

1 Like

Are you thinking the definition of "commonly used" would be based on the % of total Nano held in each tier? If so I agree and this seems the most fair/logical way to determine how often the selector stops at each tier.

I assume a table of total balance per tier could be pulled every so often from the ledger? Or could it be dynamically tracked with each confirmed block? Either way I do worry it could lead to some inconsistency between nodes in what exact table they are working from (could be very marginal) and how exactly the selector pattern gets programmed.

One thought was that perhaps the selector takes more than 1 block at a time for higher balance tiers, but that alone probably isn't enough since this would require a tiny fraction of a block from very lower tier nodes (obviously, you can't pull a fraction of a block).

1 Like

Reading my last reply, is there a big advantage to using 128 tiers and the leading zeros approach? If not, would it be better for each node to periodically access the ledger (even once a month seems reasonable) and realign the max/min of each tier so the accounts in each tier held 128th (or some optimal number) of the total Nano supply?

It seems this would let the selector run in order through the tiers pulling one block from each. Those accounts with a very small balance would be in competition with many more accounts for each "turn", those accounts with a very large balance would have little if any competition.

I could see there being some disagreement between nodes about accounts on the max or min line for each tier but again this seems marginal. There could be some gamesmanship of account holders as to whether they should split or combine their accounts given the changing max/min cutoffs of each tier but I would imagine for the bulk of honest accounts there would not be a big incentive to make the effort.

1 Like