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

prospective parachains API chain: Provide N candidates #3129

Closed
Tracked by #1829
eskimor opened this issue Jan 30, 2024 · 3 comments · Fixed by #3160
Closed
Tracked by #1829

prospective parachains API chain: Provide N candidates #3129

eskimor opened this issue Jan 30, 2024 · 3 comments · Fixed by #3160
Assignees

Comments

@eskimor
Copy link
Member

eskimor commented Jan 30, 2024

Don't only provide one candidate, but N, where N is given in the message. Implementation: simple replacement of next() with take(N).

@alindima alindima self-assigned this Jan 31, 2024
@alindima
Copy link
Contributor

alindima commented Jan 31, 2024

I think it's more complicated than a simple replacement with take(N). The current implementation always takes the first available node.
For multiple candidates, we need to return a chain of valid candidates, of the requested size. So we need to do a depth-first search through the tree. If we can't find a chain of N candidates, we should return the chain of the maximum size we could find instead. Any exhaustive search would work but I think dept-first is more suited because we can be optimistic that collators are cooperating and there's only one valid option (and therefore complexity would be O(N) usually)

@eskimor
Copy link
Member Author

eskimor commented Jan 31, 2024

Err on what is the cheapest for the validators in the worst case (non cooperating collators). We don't have to find an optimal solution, if the parachain is producing forks.

@alindima
Copy link
Contributor

alindima commented Feb 1, 2024

I guess it's no harm in accepting some amount of forks coming from collators. After all, if that weren't the case, the entire fragment trees concept could have been replaced with fragment "chains".
I implemented a depth-first search as part of my PR, but it's bounded by the requested candidate count (which shouldn't be more than two or three). So I think it's a decent solution, which would still permit having forks in the parachains, let me know your thoughts

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

Successfully merging a pull request may close this issue.

2 participants