Steem Witness Scheduling Algorithm
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.
I downvoted the post not because I disagree with the post or think it is not a quality post but because I do not think that the interests of Steem are served by every platform or devteam update or request for community feedback pulling thousands of dollars from the reward pools that go to ordinary users. The reward consensus algorithm also disproportionately rewards these posts since they are the only thing that 100% of Steem users have in common (aside from being human, etc.).
This is a reply to an old post but this is an important and prescient point. For Steemit's long term health, these types of posts shouldn't get huge votes. They uniformly go up to similar people for similar content. It's useful and important but if the rewards get siloed on these posts, it's bad for the ecosystem. Thanks.
I think you are wrong in this reasoning. Which wouldn't be a problem if in this particular case you were not wrong (according to me) in a way that is detrimental to your stated objectives ! Which is a bit of a paradox. You are not simply wrong, you are 180° wrong. You take an action that you think advances toward an objective. That action could "perfect", or "quite good" or "not that good" or "not good" ...
But here your action is "100% terrible" - it's the worst thing one could have done given your objectives (serving the interests of Steem)
Curious if you notice this comment and if you could be bothered to listen to the "why I believe that"
I notice your comment but I'm not particularly interested in rehashing an issue from two years ago, particularly given significant differences in how the platform operates now compared to then.
Thank you for your answer - do you mean that what is explained in this article is not anymore the way witnesses below 20 are selected / scheduled to produce blocks ? If that is what you mean, would you be so kind and direct me to more recent / accurate information ? I want to start a witness node and I'm therefore very interested in this topic: how often does a witness (below the first 20) get to append a block ? Has the selection algorithm changed ?
Thanks in advance!
I do not believe the witness scheduling has changed significantly. However, if the exactly algorithm is important to you the only way to be sure you are getting the precise details right is to review the current source code.
Thanks. No, knowing the exact algorithm is not a priority, we'll see by doing because we have already begun the process of setting up a witness node
With this block_num based scheduling algorithm, if a witness missed its block in a round, the first one in the shuffled list will get chance to produce one more block?
Yes
missed block should assign to running witness (20-21)in the queue in order to attract more miners
This never made sense to me.