The Steem witness scheduling algorithm is designed to pick 21 witnesses to sign the next 21 blocks. There are three ways that an witness can be selected:
- Be in the top 19 by total approval voting
- Be the next in line in the POW queue
- Be the witness with the lowest virtual_scheduled_time
If a witness is any where in the POW queue they are excluded from being selected by one of the other two methods.
If a witness is in the top 19 by total approval voting, they are excluded from being selected by virtual_scheduled_time.
Every 21 blocks is considered a “round” and this algorithm is executed at the start of each round.
Understanding Virtual Time
Imagine a very long race track such that even the fastest possible car takes 1000 seconds to complete a lap. Imagine that a witness’ votes are its speed. The virtual_scheduled_time is the time at which a witness will complete its lap and get added to a round.
Every time a witness completes a lap, they are scheduled to produce a block. The witness with the lowest
virtual_scheduled_time is next one to be included in a round. When they are scheduled, the global
current_virtual_time is updated.
Every time a witness’ vote changes, their position on the race track is updated based upon the virtual time elapsed since their last update and their velocity (votes) over that same time period. Once their new position and velocity are adjusted a new virtual_scheduled_time is calculated.
Updating the Witness Schedule
The first step is to iterate over witnesses sorted by total vote and add them to the active set until the active set reaches 19. If any witness is in the POW queue they are skipped during this phase. For each of these witnesses their virtual_scheduled_time is set to “infinity” or the maximum allowed so that they are not selected by subsequent steps.
The second step is to fetch the witness with the lowest virtual_scheduled_time that isn’t in the POW queue. Virtual scheduled time starts out initialized at infinity for miners and new witnesses and only gets set to something lower when there are votes.
Once the witness is identified, the current virtual time is set to its scheduled time. Its virtual position gets reset to 0 (start of lap) and it is assigned a new virtual scheduled time based upon its velocity (aka votes).
At this point the network has assigned 20 of 21 witnesses.
If there are at least 21 POW witnesses in the queue (and there should always be) then the top POW worker is popped by setting the pow_worker property to 0 and decreasing the num_pow_witnesses. pow_worker represents the total cumulative pow work measured as the sum of queue length at the time each POW is solved. A value of 0 is reserved to mean “unscheduled”, otherwise all witnesses are guaranteed to be sorted by this field.
By fetching the lowest pow_worker greater than 0 ( index.upper_bound(0) ) we can find the POW worker that should be included in the block.
Shuffling Active Set
After 21 witnesses have been selected, they are shuffled using the block time as a seed to a random number generator.
Potential Future Improvements
This algorithm makes the assumption that all witnesses with votes are "active" and ready to produce blocks. A witness should have to prove they are online within the 24 hours before they get scheduled. This would maximize network reliability.