Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Sorting Algorithm and Fairness in Validator Seat Allocation #271

Open
soaresa opened this issue Jul 8, 2024 · 0 comments
Open

Sorting Algorithm and Fairness in Validator Seat Allocation #271

soaresa opened this issue Jul 8, 2024 · 0 comments
Assignees

Comments

@soaresa
Copy link
Contributor

soaresa commented Jul 8, 2024

Describe the bug
When the number of seats for the next epoch decreases, and a group of eligible validators have the same lowest bid, the selection process lacks fairness. For example, consider validators v1, v2, v3, v4, and v5 with bids of 500, 250, 10, 10, and 10, respectively. The issue arises because there is no randomness in selecting which of the lowest bid validators will be excluded from the set.

Expected behavior
The expected behavior is that validators with the same bid value should have an equal chance of being included or excluded from the validator set, ensuring a fair selection process for each epoch.

Technical Analysis
Currently, eligible validators are sorted by bid using a bubble sort algorithm. After sorting, the list is reversed, creating a list X with the highest bids first and the lowest bids last. Validators are selected from left to right in list X until all seats are filled.

The problem with bubble sort is that it does not change the position of elements with equal values. Thus, if multiple validators have the same bid, the one that appears first will always remain in its position. When the sorted list is reversed, the first validator with the lowest bid will always be excluded.

Solution
With the recent addition of a random number generation module, we can create a function that ensures randomness among validators with the same bid value. This will ensure fairness in selecting which validators are included or excluded from the set in each epoch.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant