Search Results

Documents authored by Fernández Anta, Antonio

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}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.5
Tight Conditions for Binary-Output Tasks Under Crashes

Authors: Timothé Albouy, Antonio Fernández Anta, Chryssis Georgiou, Nicolas Nicolaou, and Junlang Wang

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
This paper explores necessary and sufficient system conditions to solve distributed tasks with binary outputs (i.e., tasks with output values in {0,1}). We focus on the distinct output sets of values a task can produce (intentionally disregarding validity and value multiplicity), considering that some processes may output no value. In a distributed system with n processes, of which up to t ≤ n can crash, we provide a complete characterization of the tight conditions on n and t under which every class of tasks with binary outputs is solvable, for both synchronous and asynchronous systems. This output-set approach yields highly general results: it unifies multiple distributed computing problems, such as binary consensus and symmetry breaking, and it produces impossibility proofs that hold for stronger task formulations, including those that consider validity, account for value multiplicity, or move beyond binary outputs.
Cite as

Timothé Albouy, Antonio Fernández Anta, Chryssis Georgiou, Nicolas Nicolaou, and Junlang Wang. Tight Conditions for Binary-Output Tasks Under Crashes. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.OPODIS.2025.5,
  author =	{Albouy, Timoth\'{e} and Fern\'{a}ndez Anta, Antonio and Georgiou, Chryssis and Nicolaou, Nicolas and Wang, Junlang},
  title =	{{Tight Conditions for Binary-Output Tasks Under Crashes}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.5},
  URN =		{urn:nbn:de:0030-drops-251786},
  doi =		{10.4230/LIPIcs.OPODIS.2025.5},
  annote =	{Keywords: Distributed solvability, Asynchrony, Synchrony, Impossibility proofs, Binary-output tasks, Crash tolerance, Disagreement}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.4
AMECOS: A Modular Event-Based Framework for Concurrent Object Specification

Authors: Timothé Albouy, Antonio Fernández Anta, Chryssis Georgiou, Mathieu Gestin, Nicolas Nicolaou, and Junlang Wang

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
In this work, we introduce a modular framework for specifying distributed systems that we call AMECOS. Specifically, our framework departs from the traditional use of sequential specification, which presents limitations both on the specification expressiveness and implementation efficiency of inherently concurrent objects, as documented by Castañeda, Rajsbaum and Raynal in CACM 2023. Our framework focuses on the interactions between the various system components, specified as concurrent objects. Interactions are described with sequences of object events. This provides a modular way of specifying distributed systems and separates legality (object semantics) from other issues, such as consistency. We demonstrate the usability of our framework by (i) specifying various well-known concurrent objects, such as registers, shared memory, message-passing, reliable broadcast, and consensus, (ii) providing hierarchies of ordering semantics (namely, consistency hierarchy, memory hierarchy, and reliable broadcast hierarchy), and (iii) presenting a novel axiomatic proof of the impossibility of the well-known Consensus problem.
Cite as

Timothé Albouy, Antonio Fernández Anta, Chryssis Georgiou, Mathieu Gestin, Nicolas Nicolaou, and Junlang Wang. AMECOS: A Modular Event-Based Framework for Concurrent Object Specification. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 4:1-4:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.OPODIS.2024.4,
  author =	{Albouy, Timoth\'{e} and Fern\'{a}ndez Anta, Antonio and Georgiou, Chryssis and Gestin, Mathieu and Nicolaou, Nicolas and Wang, Junlang},
  title =	{{AMECOS: A Modular Event-Based Framework for Concurrent Object Specification}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{4:1--4:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.4},
  URN =		{urn:nbn:de:0030-drops-225409},
  doi =		{10.4230/LIPIcs.OPODIS.2024.4},
  annote =	{Keywords: Concurrency, Object specification, Consistency conditions, Consensus impossibility}
}
Document
DOI: 10.4230/OASIcs.FAB.2021.2
Byzantine-Tolerant Distributed Grow-Only Sets: Specification and Applications

Authors: Vicent Cholvi, Antonio Fernández Anta, Chryssis Georgiou, Nicolas Nicolaou, Michel Raynal, and Antonio Russo

Published in: OASIcs, Volume 92, 4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021)

Abstract
In order to formalize Distributed Ledger Technologies and their interconnections, a recent line of research work has formulated the notion of Distributed Ledger Object (DLO), which is a concurrent object that maintains a totally ordered sequence of records, abstracting blockchains and distributed ledgers. Through DLO, the Atomic Appends problem, intended as the need of a primitive able to append multiple records to distinct ledgers in an atomic way, is studied as a basic interconnection problem among ledgers. In this work, we propose the Distributed Grow-only Set object (DSO), which instead of maintaining a sequence of records, as in a DLO, maintains a set of records in an immutable way: only Add and Get operations are provided. This object is inspired by the Grow-only Set (G-Set) data type which is part of the Conflict-free Replicated Data Types. We formally specify the object and we provide a consensus-free Byzantine-tolerant implementation that guarantees eventual consistency. We then use our Byzantine-tolerant DSO (BDSO) implementation to provide consensus-free algorithmic solutions to the Atomic Appends and Atomic Adds (the analogous problem of atomic appends applied on G-Sets) problems, as well as to construct consensus-free Single-Writer BDLOs. We believe that the BDSO has applications beyond the above-mentioned problems.
Cite as

Vicent Cholvi, Antonio Fernández Anta, Chryssis Georgiou, Nicolas Nicolaou, Michel Raynal, and Antonio Russo. Byzantine-Tolerant Distributed Grow-Only Sets: Specification and Applications. In 4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021). Open Access Series in Informatics (OASIcs), Volume 92, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cholvi_et_al:OASIcs.FAB.2021.2,
  author =	{Cholvi, Vicent and Fern\'{a}ndez Anta, Antonio and Georgiou, Chryssis and Nicolaou, Nicolas and Raynal, Michel and Russo, Antonio},
  title =	{{Byzantine-Tolerant Distributed Grow-Only Sets: Specification and Applications}},
  booktitle =	{4th International Symposium on Foundations and Applications of Blockchain 2021 (FAB 2021)},
  pages =	{2:1--2:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-196-2},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{92},
  editor =	{Gramoli, Vincent and Sadoghi, Mohammad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.FAB.2021.2},
  URN =		{urn:nbn:de:0030-drops-139883},
  doi =		{10.4230/OASIcs.FAB.2021.2},
  annote =	{Keywords: Grow-only Sets, Distributed Ledgers, Blockchains, Atomic appends}
}
Document
DOI: 10.4230/OASIcs.Tokenomics.2019.5
Atomic Appends: Selling Cars and Coordinating Armies with Multiple Distributed Ledgers

Authors: Antonio Fernández Anta, Chryssis Georgiou, and Nicolas Nicolaou

Published in: OASIcs, Volume 71, International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019)

Abstract
The various applications using Distributed Ledger Technologies (DLT) or blockchains, have led to the introduction of a new "marketplace" where multiple types of digital assets may be exchanged. As each blockchain is designed to support specific types of assets and transactions, and no blockchain will prevail, the need to perform interblockchain transactions is already pressing. In this work we examine the fundamental problem of interoperable and interconnected blockchains. In particular, we begin by introducing the Multi-Distributed Ledger Objects (MDLO), which is the result of aggregating multiple Distributed Ledger Objects - DLO (a DLO is a formalization of the blockchain) and that supports append and get operations of records (e.g., transactions) in them from multiple clients concurrently. Next we define the AtomicAppends problem, which emerges when the exchange of digital assets between multiple clients may involve appending records in more than one DLO. Specifically, AtomicAppend requires that either all records will be appended on the involved DLOs or none. We examine the solvability of this problem assuming rational and risk-averse clients that may fail by crashing, and under different client utility and append models, timing models, and client failure scenarios. We show that for some cases the existence of an intermediary is necessary for the problem solution. We propose the implementation of such intermediary over a specialized blockchain, we term Smart DLO (SDLO), and we show how this can be used to solve the AtomicAppends problem even in an asynchronous, client competitive environment, where all the clients may crash.
Cite as

Antonio Fernández Anta, Chryssis Georgiou, and Nicolas Nicolaou. Atomic Appends: Selling Cars and Coordinating Armies with Multiple Distributed Ledgers. In International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019). Open Access Series in Informatics (OASIcs), Volume 71, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fernandezanta_et_al:OASIcs.Tokenomics.2019.5,
  author =	{Fern\'{a}ndez Anta, Antonio and Georgiou, Chryssis and Nicolaou, Nicolas},
  title =	{{Atomic Appends: Selling Cars and Coordinating Armies with Multiple Distributed Ledgers}},
  booktitle =	{International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019)},
  pages =	{5:1--5:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-108-5},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{71},
  editor =	{Danos, Vincent and Herlihy, Maurice and Potop-Butucaru, Maria and Prat, Julien and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2019.5},
  URN =		{urn:nbn:de:0030-drops-119695},
  doi =		{10.4230/OASIcs.Tokenomics.2019.5},
  annote =	{Keywords: DLO, Interoperability, Atomic Appends, Rational Clients, Fault-tolerance}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.29
Computationally Light "Multi-Speed" Atomic Memory

Authors: Antonio Fernández Anta, Theophanis Hadjistasi, and Nicolas Nicolaou

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Communication demands are usually the leading factor that defines the efficiency of operations on a read/write shared memory emulation in the message-passing environment. In the quest for minimizing the communication demands, the algorithms proposed either require restrictions in the system or incur high computation demands. As a result, such solutions may be not suitable to be used in practice. In this paper we focus on the practicality of implementations of atomic read/write shared memory emulation in the message-passing environment. In particular we investigate implementations that reduce both communication and computation demands. We first examine the shortcomings of the best two (in terms of communication demands) known algorithms that implement atomic single-writer multiple-reader (SWMR) atomic memory. The algorithm ccFast proposed by A. Fernández et al., achieves optimal communication by allowing each operation to complete in one round trip, with light computation requirements. Unfortunately, it relies on strict limitations on the number of readers. On the other hand, algorithm OhSam, imposes no restrictions on the system, but provides operations that require one and a half communication rounds. In the light of these shortcomings, we present two algorithms that implement multi-speed operations with light computation, and without imposing any restriction on the system. In particular, algorithm ccHybrid adopts the fast (one-round) writes and makes clients to switch to a slow (two-round) mode whenever the system is congested. On the other hand, algorithm OhFast, pushes the responsibility of deciding for the speed switch to the servers. This allows the algorithm to utilize the fast operations, and the slow one-and-a-half-rounds operations of the algorithm presented by T. Hadjistasi et al., whenever is necessary. We prove that both new algorithms preserve atomicity. To evaluate the new algorithms we implement five different atomic memory algorithms in the NS3 simulator, and we compare their performance in terms of operation latency, and ratio of slow over fast operations performed. We test the algorithms over different: (i) topologies, and (ii) operation loads. Our results support that the newly presented algorithms increase the practicality of atomic read/write atomic shared memory implementations in the message-passing, asynchronous environment.
Cite as

Antonio Fernández Anta, Theophanis Hadjistasi, and Nicolas Nicolaou. Computationally Light "Multi-Speed" Atomic Memory. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{fernandezanta_et_al:LIPIcs.OPODIS.2016.29,
  author =	{Fern\'{a}ndez Anta, Antonio and Hadjistasi, Theophanis and Nicolaou, Nicolas},
  title =	{{Computationally Light "Multi-Speed" Atomic Memory}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.29},
  URN =		{urn:nbn:de:0030-drops-70980},
  doi =		{10.4230/LIPIcs.OPODIS.2016.29},
  annote =	{Keywords: atomicity, read/write objects, shared memory, operation latency}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.19
Making "Fast" Atomic Operations Computationally Tractable

Authors: Antonio Fernández Anta, Nicolas Nicolaou, and Alexandru Popa

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Communication overhead is the most commonly used performance metric for the operation complexity of distributed algorithms in message-passing environments. However, aside with communication, many distributed operations utilize complex computations to reach their desired outcomes. Therefore, a most accurate operation latency measure should account of both computation and communication metrics. In this paper we focus on the efficiency of read and write operations in an atomic read/write shared memory emulation in the message-passing environment. We examine the operation complexity of the best known atomic register algorithm, that allows all read and write operations to complete in a single communication round-trip. Such operations are called fast. At its heart, the algorithm utilizes a predicate to allow processes to compute their outcome. We show that the predicate used is computationally hard, by devising a computationally equivalent problem and reducing that to Maximum Biclique, a known NP-hard problem. To improve the computational complexity of the algorithm we derive a new predicate that leads to a new algorithm, we call ccFast, and has the following properties: (i) can be computed in polynomial time, rendering each read operation in ccFast tractable compared to the read operations in the original algorithm, (ii) the messages used in ccFast are reduced in size, compared to the original algorithm, by almost a linear factor, (iii) allows all operations in ccFast to be fast, and (iv) allows ccFast to preserve atomicity. A linear time}algorithm for the computation of the new predicate is presented along with an analysis of the message complexity of the new algorithm. We believe that the new algorithm redefines the term fast capturing both the communication and the computation metrics of each operation.
Cite as

Antonio Fernández Anta, Nicolas Nicolaou, and Alexandru Popa. Making "Fast" Atomic Operations Computationally Tractable. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fernandezanta_et_al:LIPIcs.OPODIS.2015.19,
  author =	{Fern\'{a}ndez Anta, Antonio and Nicolaou, Nicolas and Popa, Alexandru},
  title =	{{Making "Fast" Atomic Operations Computationally Tractable}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.19},
  URN =		{urn:nbn:de:0030-drops-66108},
  doi =		{10.4230/LIPIcs.OPODIS.2015.19},
  annote =	{Keywords: atomicity, read/write objects, shared memory, computational complexity}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact