Blockchains such as Solana, Sui, and Aptos execute the transactions of a block in parallel, serialising only those that conflict on shared state. In earlier work, we brought this parallelism into block building itself with the Parallel-Block Construction problem. There, the builder selects transactions from the mempool and schedules them on multiple cores within a gas budget, so that the choice of transactions and the available parallelism are decided together. In this talk, I will examine how hard this problem is to solve, optimally or approximately. Its complexity changes sharply with small changes to the setting. Depending on the number of cores and the allowed execution times, the problem moves between exact polynomial-time solvability, NP-hardness, and strong inapproximability. I will present the hardness reductions and the matching- and greedy-based approximation algorithms behind these boundaries. I will also show experiments on Ethereum mainnet traces, where the algorithms come much closer to optimal than their worst-case guarantees suggest.

About Arivarasan Karmegam

Arivarasan Karmegam is a predoctoral researcher at IMDEA Networks Institute and a final-year PhD student in Telematics Engineering at UC3M. He is supervised by Dr. Antonio Fernández Anta. His research is on distributed systems and blockchain scalability. Before his PhD, Arivarasan earned an M.Tech in Computer Science and Engineering from the Indian Institute of Technology Dhanbad, India, and a B.E. in Computer Science and Engineering from Ramco Institute of Technology, India.

Este evento se impartirá en inglés