DROPS

Document

DOI: 10.4230/LIPIcs.AFT.2026.9

Approximation and Hardness Results for the Parallel-Block Construction Problem

Authors: Arivarasan Karmegam, Alexandru Popa, Lucianna Kiffer, and Antonio Fernández Anta

Published in: LIPIcs, Volume 395, 8th Conference on Advances in Financial Technologies (AFT 2026)

Abstract

Several high-throughput blockchains, including Solana, Sui, and Aptos, execute transactions in parallel across multiple cores to improve throughput and reduce latency. However, transaction conflicts induced by shared state access fundamentally couple block construction with parallel scheduling. We formalize and study the Parallel-Block Construction problem: given transactions with execution times, rewards, and conflict relations, select and schedule a subset of transactions on p parallel cores within a runtime (gas) budget to maximize total reward. We provide a comprehensive analysis of the complexity and approximation landscape for this problem. When the number of cores p is part of the input, we prove strong inapproximability via a reduction from Maximum Clique: unless NP = ZPP, no polynomial-time algorithm achieves an n^{1-ε}-approximation for any ε > 0. For constant p and uniform processing times, we give a greedy algorithm achieving a tight (1 - 1/e)-approximation ratio. We further establish NP-completeness even for fixed p = 4 and unit-length transactions, and show that for p = 2 the problem admits an exact polynomial-time algorithm via a reduction to maximum-weight matching (with a cardinality constraint). In contrast, allowing heterogeneous processing times restores hardness: the problem becomes NP-complete for p = 2 with processing times in {1,3} (even with unit rewards). For p = 2 and processing times in {1,2}, we design a polynomial-time (2/3-δ)-approximation algorithm (for any δ > 0) via a structural decomposition and a reduction to a budgeted matching problem. We validate our theoretical results with experiments on Ethereum mainnet execution traces. In the homogeneous setting, our (1-1/e)-approximation algorithm almost always achieves rewards above 99% of the MILP-based optimal baseline, far exceeding the guaranteed factor of 1-1/e = 0.63. In the heterogeneous setting (p = 2, processing times in {1,2}), the non-overlap variant achieves above 99% of the optimal across all tested configurations, confirming that the theoretical 2/3 bound is a pessimistic worst-case guarantee that does not reflect typical performance on real workloads.

Cite as

Arivarasan Karmegam, Alexandru Popa, Lucianna Kiffer, and Antonio Fernández Anta. Approximation and Hardness Results for the Parallel-Block Construction Problem. In 8th Conference on Advances in Financial Technologies (AFT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 395, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karmegam_et_al:LIPIcs.AFT.2026.9,
  author =	{Karmegam, Arivarasan and Popa, Alexandru and Kiffer, Lucianna and Fern\'{a}ndez Anta, Antonio},
  title =	{{Approximation and Hardness Results for the Parallel-Block Construction Problem}},
  booktitle =	{8th Conference on Advances in Financial Technologies (AFT 2026)},
  pages =	{9:1--9:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-451-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{395},
  editor =	{Kiayias, Aggelos and Kyropoulou, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2026.9},
  URN =		{urn:nbn:de:0030-drops-278637},
  doi =		{10.4230/LIPIcs.AFT.2026.9},
  annote =	{Keywords: Blockchain, Parallel Execution, NP-Completeness, Approximation Algorithms}
}

Document

DOI: 10.4230/LIPIcs.SEA.2026.23

Exploiting Multi-Core Parallelism in Blockchain Validation and Construction

Authors: Arivarasan Karmegam, Lucianna Kiffer, and Antonio Fernández Anta

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract

Blockchain validators can reduce block processing time by exploiting multi-core CPUs, but deterministic execution must preserve a given total order while respecting transaction conflicts and per-block runtime limits. This paper systematically examines how validators can exploit multi-core parallelism during both block construction and execution without violating blockchain semantics. We formalize two validator-side optimization problems: (i) executing an already ordered block on p cores to minimize makespan while ensuring equivalence to sequential execution; and (ii) selecting and scheduling a subset of mempool transactions under a runtime limit B to maximize validator reward. For both, we develop exact Mixed-Integer Linear Programming (MILP) formulations that capture conflict, order, and capacity constraints, and propose fast deterministic heuristics that scale to realistic workloads. Using Ethereum mainnet traces and including a Solana-inspired declared-access baseline (Sol) for ordered-block scheduling and a simple reward-greedy baseline (RG) for block construction, we empirically quantify the trade-offs between optimality and runtime. MILPs quickly become intractable as heterogeneity or core count increases, whereas our heuristics run in milliseconds and achieve near-optimal quality. For ordered-block execution, heuristic makespans are typically within a few percent of the MILP solutions (and can even surpass the MILP incumbent when the solver times out), yielding up to 1.5 speedup with p = 2 and 2.3 speedup with p = 8 over sequential execution, despite tight ordering constraints. For block construction, the heuristic achieves 99-100% of the MILP optimum reward on homogeneous workloads, and 74-100% of an LP-relaxation upper bound on heterogeneous workloads, where exact optimization often times out. The resulting block-construction throughput scales close to linearly with p, reaching up to 7.9 speedup with p = 8 in our experiments. These results demonstrate that lightweight, conflict-aware scheduling and selection can unlock substantial parallelism in blockchain validation, bridging the gap between sequential execution and the true potential of multi-core hardware.

Cite as

Arivarasan Karmegam, Lucianna Kiffer, and Antonio Fernández Anta. Exploiting Multi-Core Parallelism in Blockchain Validation and Construction. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karmegam_et_al:LIPIcs.SEA.2026.23,
  author =	{Karmegam, Arivarasan and Kiffer, Lucianna and Fern\'{a}ndez Anta, Antonio},
  title =	{{Exploiting Multi-Core Parallelism in Blockchain Validation and Construction}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{23:1--23:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.23},
  URN =		{urn:nbn:de:0030-drops-260271},
  doi =		{10.4230/LIPIcs.SEA.2026.23},
  annote =	{Keywords: Block construction, Block execution, Deterministic parallelism, Conflict-aware scheduling}
}

Search Results

Documents authored by Karmegam, Arivarasan

Approximation and Hardness Results for the Parallel-Block Construction Problem

Abstract

Cite as

Exploiting Multi-Core Parallelism in Blockchain Validation and Construction

Abstract

Cite as

Thanks for your feedback!

Could not send message