search

ava-labs / hypersdk

Opinionated Framework for Building Hyper-Scalable Blockchains on Avalanche
https://hypersdk.xyz/
Other
190 stars 94 forks source link

Implement Chunk Packing Algorithm over MDF #997

Open patrick-ogrady opened 1 month ago

patrick-ogrady commented 1 month ago

Currently, we use FIFO to pack blocks/chunks. This is nowhere near an optimal strategy to pack blocks/chunks (especially with #717).

We should devise some algorithm that is better at packing (maybe based on Dominant Resource Fairness if we can show it is robust in a BFT environment).

patrick-ogrady commented 1 month ago

If we use DRF, we can create a single heap per epoch and discard said heap once transactions from an epoch can no longer be included (this avoids needing to do a double-heap [expiry + priority-fee weighted, dominant share]).

patrick-ogrady commented 1 month ago

This may also be a good source: https://www.statslab.cam.ac.uk/~frank/elastic.pdf

This was originally referenced in: https://arxiv.org/abs/2208.07919