DROPS

Document

DOI: 10.4230/OASIcs.FMBC.2026.8

Detecting Cross-Function Reentrancy from EVM Traces

Authors: Semia Guesmi, Carla Piazza, Andrea Gasparetto, Matteo Rizzo, and Sabina Rossi

Published in: OASIcs, Volume 142, 7th International Workshop on Formal Methods for Blockchains (FMBC 2026)

Abstract

Reentrancy remains one of the most critical vulnerabilities affecting Ethereum smart contracts. While many existing analysis tools focus on detecting classical single-function reentrancy, more complex forms such as cross-function reentrancy are harder to identify because they depend on execution semantics and interactions between multiple functions. In this work, we study reentrancy at the level of Ethereum Virtual Machine (EVM) execution traces. We extend the TxSpector framework with new Datalog-based detection rules designed to capture cross-function reentrancy patterns. To support this analysis, we also modernize the trace extraction component by adapting it to recent versions of the Ethereum client and updated EVM instructions. The proposed approach is evaluated on real Ethereum on-chain transaction traces. The results show that our method is able to detect cross-function reentrancy behaviors that are not captured by the original TxSpector rules, demonstrating the effectiveness of pattern-based logic detection at the EVM execution level.

Cite as

Semia Guesmi, Carla Piazza, Andrea Gasparetto, Matteo Rizzo, and Sabina Rossi. Detecting Cross-Function Reentrancy from EVM Traces. In 7th International Workshop on Formal Methods for Blockchains (FMBC 2026). Open Access Series in Informatics (OASIcs), Volume 142, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{guesmi_et_al:OASIcs.FMBC.2026.8,
  author =	{Guesmi, Semia and Piazza, Carla and Gasparetto, Andrea and Rizzo, Matteo and Rossi, Sabina},
  title =	{{Detecting Cross-Function Reentrancy from EVM Traces}},
  booktitle =	{7th International Workshop on Formal Methods for Blockchains (FMBC 2026)},
  pages =	{8:1--8:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-424-6},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{142},
  editor =	{Bartoletti, Massimo and Marmsoler, Diego},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.FMBC.2026.8},
  URN =		{urn:nbn:de:0030-drops-257058},
  doi =		{10.4230/OASIcs.FMBC.2026.8},
  annote =	{Keywords: Blockchain, smart contract, Reentrancy detection, EVM, design Patterns, logic rules}
}

Document

DOI: 10.4230/OASIcs.PARMA-DITAM.2026.4

Inter-Procedural Strength Reduction for Embedded Systems

Authors: Giovanni Agosta

Published in: OASIcs, Volume 141, 17th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 15th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2026)

Abstract

Embedded systems often rely on code generated from model-based design tools, which can result in inefficient implementations due to the loss of high-level semantic information during code generation. This paper explores an inter-procedural extension of the strength reduction transformation, traditionally applied within loops, to optimize repeated computations across function calls. The proposed technique identifies parameters acting as counters and replaces costly operations - such as exponentiation or multiplication - with incremental updates based on recurrence relations, using static variables to preserve state between calls. We formalize the transformation, discuss its applicability conditions, and analyse tradeoffs between computation and memory access costs. Experimental evaluation on ARMv8, AVR microcontrollers, and x86_64 platforms demonstrates significant speedups for power operations (up to 9 ×), while highlighting limitations for simpler operations due to memory overhead.

Cite as

Giovanni Agosta. Inter-Procedural Strength Reduction for Embedded Systems. In 17th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 15th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2026). Open Access Series in Informatics (OASIcs), Volume 141, pp. 4:1-4:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agosta:OASIcs.PARMA-DITAM.2026.4,
  author =	{Agosta, Giovanni},
  title =	{{Inter-Procedural Strength Reduction for Embedded Systems}},
  booktitle =	{17th Workshop on Parallel Programming and Run-Time Management Techniques for Many-Core Architectures and 15th Workshop on Design Tools and Architectures for Multicore Embedded Computing Platforms (PARMA-DITAM 2026)},
  pages =	{4:1--4:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-416-1},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{141},
  editor =	{Baroffio, Davide and Busia, Paola and Denisov, Lev and Shukla, Nitin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.PARMA-DITAM.2026.4},
  URN =		{urn:nbn:de:0030-drops-256717},
  doi =		{10.4230/OASIcs.PARMA-DITAM.2026.4},
  annote =	{Keywords: Compiler Optimization, Strength Reduction}
}

Document

Research

DOI: 10.4230/TGDK.4.1.3

Semantically Reflected Programs

Authors: Eduard Kamburjan, Vidar Norstein Klungre, Yuanwei Qu, Rudolf Schlatte, Egor V. Kostylev, Martin Giese, and Einar Broch Johnsen

Published in: TGDK, Volume 4, Issue 1 (2026). Transactions on Graph Data and Knowledge, Volume 4, Issue 1

Abstract

This paper addresses the dichotomy between the formalization of structural and the formalization of executable behavioral knowledge by means of semantically lifted programs, which explore an intuitive connection between imperative programs and knowledge graphs. While knowledge graphs and ontologies are eminently useful to represent formal knowledge about a system’s individuals and universals, programming languages are designed to describe the system’s evolution. To address this dichotomy, we introduce a semantic lifting of the program states of an executing progam into a knowledge graph, for an object-oriented programming language. The resulting graph is exposed as a semantic reflection layer within the programming language, allowing programmers to leverage knowledge of the application domain in their programs during execution. In this paper, we formalize semantic lifting and semantic reflection for a small imperative programming language, SMOL, explain the operational aspects of the language, and consider type correctness and virtualization for runtime program queries through the semantic reflection layer. We illustrate semantic lifting and semantic reflection through a case study of geological modeling and discuss different applications of the technique. The language implementation is open source and available online.

Cite as

Eduard Kamburjan, Vidar Norstein Klungre, Yuanwei Qu, Rudolf Schlatte, Egor V. Kostylev, Martin Giese, and Einar Broch Johnsen. Semantically Reflected Programs. In Transactions on Graph Data and Knowledge (TGDK), Volume 4, Issue 1, pp. 3:1-3:52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{kamburjan_et_al:TGDK.4.1.3,
  author =	{Kamburjan, Eduard and Klungre, Vidar Norstein and Qu, Yuanwei and Schlatte, Rudolf and Kostylev, Egor V. and Giese, Martin and Johnsen, Einar Broch},
  title =	{{Semantically Reflected Programs}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:52},
  ISSN =	{2942-7517},
  year =	{2026},
  volume =	{4},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.4.1.3},
  URN =		{urn:nbn:de:0030-drops-256884},
  doi =		{10.4230/TGDK.4.1.3},
  annote =	{Keywords: Knowledge Graphs, Ontologies, Object-Oriented Modelling, Imperative Programming Languages, Reflection, Type Safety}
}

Document

DOI: 10.4230/OASIcs.NINeS.2026.13

In-Kernel Aggregation and Broadcast Acceleration for Distributed Communication

Authors: Jianchang Su, Yifan Zhang, and Wei Zhang

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract

Broadcasting and aggregation dominate the communication overhead in distributed systems, from machine learning training to data analytics. Current acceleration approaches require specialized hardware (RDMA) or dedicated resources (DPDK), limiting their deployment in commodity clouds. However, we present a counter-intuitive alternative: rather than bypassing the kernel, we move operations into it using eBPF. While this imposes severe constraints including no floating-point, limited memory, and stateless execution, we show these restrictions paradoxically drive innovative protocol designs that yield unexpected benefits. We introduce AggBox, which implements broadcast and aggregation operations entirely within eBPF’s constrained environment. Our key innovations include stateless group acknowledgments for reliability, edge quantization for floating-point aggregation using only integer arithmetic, and tail-call chains that create virtual memory beyond eBPF’s 512-byte stack limit. These designs emerge from and exploit the constraints rather than fighting them. AggBox achieves remarkable performance on commodity hardware: 84.5% reduction in broadcast latency, 43× speedup for MapReduce workloads, and 56.1% faster ML gradient aggregation, all without specialized NICs or dedicated cores. Beyond performance, our work demonstrates that constrained environments can drive fundamental innovation in protocol design, offering insights for future resource-limited and verified systems.

Cite as

Jianchang Su, Yifan Zhang, and Wei Zhang. In-Kernel Aggregation and Broadcast Acceleration for Distributed Communication. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{su_et_al:OASIcs.NINeS.2026.13,
  author =	{Su, Jianchang and Zhang, Yifan and Zhang, Wei},
  title =	{{In-Kernel Aggregation and Broadcast Acceleration for Distributed Communication}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{13:1--13:23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.13},
  URN =		{urn:nbn:de:0030-drops-255981},
  doi =		{10.4230/OASIcs.NINeS.2026.13},
  annote =	{Keywords: eBPF, distributed communication, broadcast, aggregation, in-kernel processing, XDP}
}

Document

DOI: 10.4230/OASIcs.NINeS.2026.19

Simulate Before Sending: Rethinking Transport in Datacenter Networks

Authors: Dan Straussman, Isaac Keslassy, Alexander Shpiner, and Liran Liss

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract

Existing transport protocols in commodity datacenter networks struggle to provide low collective completion times (CCTs) to AI training collectives, as packet losses and retransmissions significantly degrade performance. We propose dcSim, an efficient transport that achieves low CCTs and practically lossless performance with commodity switches. In dcSim, each packet first employs a small simulation probe to traverse the network and explore congestion along a candidate path. Only packets whose simulation probes succeed are then transmitted, expecting to succeed as well. Evaluations confirm that dcSim achieves faster CCTs than existing schemes, with small queues and virtually zero packet loss. Finally, dcSim also excels in adverse conditions, including oversubscribed topologies.

Cite as

Dan Straussman, Isaac Keslassy, Alexander Shpiner, and Liran Liss. Simulate Before Sending: Rethinking Transport in Datacenter Networks. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 19:1-19:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{straussman_et_al:OASIcs.NINeS.2026.19,
  author =	{Straussman, Dan and Keslassy, Isaac and Shpiner, Alexander and Liss, Liran},
  title =	{{Simulate Before Sending: Rethinking Transport in Datacenter Networks}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{19:1--19:22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.19},
  URN =		{urn:nbn:de:0030-drops-256044},
  doi =		{10.4230/OASIcs.NINeS.2026.19},
  annote =	{Keywords: Datacenter networks, transport protocols, AI training, lossless networks}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.93

Analyzing the Economic Impact of Decentralization on Users

Authors: Amit Levy, S. Matthew Weinberg, and Chenghan Zhou

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We model the ultimate price paid by users of a decentralized ledger as resulting from a two-stage game where Miners (/Proposers/etc.) first purchase blockspace via a Tullock contest, and then price that space to users. When analyzing our distributed ledger model, we find: - A characterization of all possible pure equilibria (although pure equilibria are not guaranteed to exist). - A natural sufficient condition, implied by Regularity (à la [Myerson, 1981]), for existence of a "market-clearing" pure equilibrium where Miners choose to sell all space allocated by the Distributed Ledger Protocol, and that this equilibrium is unique. - The market share of the largest miner is the relevant "measure of decentralization" to determine whether a market-clearing pure equilibrium exists. - Block rewards do not impact users' prices at equilibrium, when pure equilibria exist. But, higher block rewards can cause pure equilibria to exist. We also discuss aspects of our model and how they relate to blockchains deployed in practice. For example, only "patient" users (who are happy for their transactions to enter the blockchain under any miner) would enjoy the conclusions highlighted by our model, whereas "impatient" users (who are interested only for their transaction to be included in the very next block) still face monopoly pricing.

Cite as

Amit Levy, S. Matthew Weinberg, and Chenghan Zhou. Analyzing the Economic Impact of Decentralization on Users. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 93:1-93:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{levy_et_al:LIPIcs.ITCS.2026.93,
  author =	{Levy, Amit and Weinberg, S. Matthew and Zhou, Chenghan},
  title =	{{Analyzing the Economic Impact of Decentralization on Users}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{93:1--93:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.93},
  URN =		{urn:nbn:de:0030-drops-253805},
  doi =		{10.4230/LIPIcs.ITCS.2026.93},
  annote =	{Keywords: Blockchain, Cryptocurrency, Blockspace Markets, Decentralization, Distributed Ledgers, Equilibrium Analysis, Tullock Contests}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.116

Decentralized Data Archival: New Definitions and Constructions

Authors: Elaine Shi, Rose Silver, and Changrui Mu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We initiate the study of a new abstraction called incremental decentralized data archival (iDDA). Specifically, imagine that there is an ever-growing, massive database such as a blockchain, a comprehensive human knowledge base like Wikipedia, or the Internet archive. We want to build a decentralized archival system for such datasets to ensure long-term robustness and sustainability. We identify several important properties that an iDDA scheme should satisfy. First, to promote heterogeneity and decentralization, we want to encourage even weak nodes with limited space (e.g., users' home computers) to contribute. The minimum space requirement to contribute should be approximately independent of the data size. Second, if a collection of nodes together receive rewards commensurate with contributing a total of m blocks of space, then we want the following reassurances: 1) if m is at least the database size, we should be able to reconstruct the entire dataset; and 2) these nodes should actually be committing roughly m space in aggregate - specifically, when m is much larger than the data size, these nodes cannot store only one copy of the database, and be able to impersonate arbitrarily many pseudonyms and get unbounded rewards. We propose new definitions that mathematically formalize the aforementioned requirements of an iDDA scheme. We also devise an efficient construction in the random oracle model which satisfies the desired security requirements. Our scheme incurs only Õ(1) audit cost, as well as Õ(1) update cost for both the publisher and each node, where Õ(⋅) hides polylogarithmic factors. Further, the minimum space provisioning required to contribute is as small as polylogarithmic. Our construction exposes several interesting technical challenges. Specifically, we show that a straightforward application of the standard hierarchical data structure fails, since both our security definition and the underlying cryptographic primitives we employ lack the desired compositional guarantees. We devise novel techniques to overcome these compositional issues, resulting in a construction with provable security while still retaining efficiency. Finally, our new definitions also make a conceptual contribution, and lay the theoretical groundwork for the study of iDDA. We raise several interesting open problems along this direction.

Cite as

Elaine Shi, Rose Silver, and Changrui Mu. Decentralized Data Archival: New Definitions and Constructions. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 116:1-116:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{shi_et_al:LIPIcs.ITCS.2026.116,
  author =	{Shi, Elaine and Silver, Rose and Mu, Changrui},
  title =	{{Decentralized Data Archival: New Definitions and Constructions}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{116:1--116:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.116},
  URN =		{urn:nbn:de:0030-drops-254037},
  doi =		{10.4230/LIPIcs.ITCS.2026.116},
  annote =	{Keywords: Decentralized Data Archival}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2025.36

BlindPerm: Efficient MEV Mitigation with an Encrypted Mempool and Permutation

Authors: Alireza Kavousi, Duc V. Le, Philipp Jovanovic, and George Danezis

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

Abstract

Maximal Extractable Value (MEV) is a crucial challenge in blockchains and cryptocurrencies. A principal countermeasure is using encrypted mempools to hide the transaction payloads until they are committed in a block. However, the existing approaches based on encrypted mempools remain vulnerable to metadata leakage and may not provide sufficient mitigation against block producers due to their sole control in block preparation. In this paper, we propose techniques that utilize randomized permutation on the committed block, offering a multi-layer solution. With a focus on proof-of-stake (PoS) committee-based consensus, we then introduce BlindPerm, a framework that enhances an encrypted mempool with permutation and present various optimizations. Notably, we propose a construction where this enhancement comes at essentially no overhead by piggybacking on the encrypted mempool and without relying on any external entity such as randomness beacon. Further, we illustrate the effectiveness of our solutions by running simulations using historical Ethereum data.

Cite as

Alireza Kavousi, Duc V. Le, Philipp Jovanovic, and George Danezis. BlindPerm: Efficient MEV Mitigation with an Encrypted Mempool and Permutation. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kavousi_et_al:LIPIcs.OPODIS.2025.36,
  author =	{Kavousi, Alireza and Le, Duc V. and Jovanovic, Philipp and Danezis, George},
  title =	{{BlindPerm: Efficient MEV Mitigation with an Encrypted Mempool and Permutation}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{36:1--36:21},
  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.36},
  URN =		{urn:nbn:de:0030-drops-252091},
  doi =		{10.4230/LIPIcs.OPODIS.2025.36},
  annote =	{Keywords: Encrypted mempool, maximal extractable value, distributed systems}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.28

Pathfinding in Self-Deleting Graphs

Authors: Michal Dvořák, Dušan Knop, Michal Opler, Jan Pokorný, Ondřej Suchý, and Krisztina Szilágyi

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

In this paper, we study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices. In particular, we study self-deleting graphs, introduced by Carmesin et al. [Sarah Carmesin et al., 2023], which consist of a graph G = (V, E) and a function f: V → 2^E, where f(v) is the set of edges that will be deleted after visiting the vertex v. In the (Shortest) Self-Deleting s-t-path problem we are given a self-deleting graph and its vertices s and t, and we are asked to find a (shortest) path from s to t, such that it does not traverse an edge in f(v) after visiting v for any vertex v. We prove that Self-Deleting s-t-path is NP-hard even if the given graph is outerplanar, bipartite, has maximum degree 3, bandwidth 2 and |f(v)| ≤ 1 for each vertex v. We show that Shortest Self-Deleting s-t-path is W[1]-complete parameterized by the length of the sought path and that Self-Deleting s-t-path is W[1]-complete parameterized by the vertex cover number, feedback vertex set number and treedepth. We also show that the problem becomes FPT when we parameterize by the maximum size of f(v) and several structural parameters. Lastly, we show that the problem does not admit a polynomial kernel even for parameterization by the vertex cover number and the maximum size of f(v) combined already on 2-outerplanar graphs.

Cite as

Michal Dvořák, Dušan Knop, Michal Opler, Jan Pokorný, Ondřej Suchý, and Krisztina Szilágyi. Pathfinding in Self-Deleting Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.ISAAC.2025.28,
  author =	{Dvo\v{r}\'{a}k, Michal and Knop, Du\v{s}an and Opler, Michal and Pokorn\'{y}, Jan and Such\'{y}, Ond\v{r}ej and Szil\'{a}gyi, Krisztina},
  title =	{{Pathfinding in Self-Deleting Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.28},
  URN =		{urn:nbn:de:0030-drops-249365},
  doi =		{10.4230/LIPIcs.ISAAC.2025.28},
  annote =	{Keywords: Parameterized complexity, self-deleting graphs, pathfinding}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.35

A Walk on the Wild Side: A Shape-First Methodology for Orthogonal Drawings

Authors: Giordano Andreola, Susanna Caroppo, Giuseppe Di Battista, Fabrizio Grosso, Maurizio Patrignani, and Allegra Strippoli

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract

Several algorithms for the construction of orthogonal drawings of graphs, including those based on the Topology-Shape-Metrics (TSM) paradigm, tend to prioritize the minimization of crossings. This emphasis has two notable side effects: some edges are drawn with unnecessarily long sequences of segments and bends, and the overall drawing area may become excessively large. As a result, the produced drawings often lack geometric uniformity. Moreover, orthogonal crossings are known to have a limited impact on readability, suggesting that crossing minimization may not always be the optimal goal. In this paper, we introduce a methodology that "subverts" the traditional TSM pipeline by focusing on minimizing bends. Given a graph G, we ideally seek to construct a rectilinear drawing of G, that is, an orthogonal drawing with no bends. When not possible, we incrementally subdivide the edges of G by introducing dummy vertices that will (possibly) correspond to bends in the final drawing. This process continues until a rectilinear drawing of a subdivision of the graph is found, after which the final coordinates are computed. We tackle the (NP-complete) rectilinear drawability problem by encoding it as a SAT formula and solving it with state-of-the-art SAT solvers. If the SAT formula is unsatisfiable, we use the solver’s proof to determine which edge to subdivide. Our implementation, domus, which is fairly simple, is evaluated through extensive experiments on small- to medium-sized graphs. The results show that it consistently outperforms ogdf’s TSM-based approach across most standard graph drawing metrics.

Cite as

Giordano Andreola, Susanna Caroppo, Giuseppe Di Battista, Fabrizio Grosso, Maurizio Patrignani, and Allegra Strippoli. A Walk on the Wild Side: A Shape-First Methodology for Orthogonal Drawings. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{andreola_et_al:LIPIcs.GD.2025.35,
  author =	{Andreola, Giordano and Caroppo, Susanna and Di Battista, Giuseppe and Grosso, Fabrizio and Patrignani, Maurizio and Strippoli, Allegra},
  title =	{{A Walk on the Wild Side: A Shape-First Methodology for Orthogonal Drawings}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.35},
  URN =		{urn:nbn:de:0030-drops-250218},
  doi =		{10.4230/LIPIcs.GD.2025.35},
  annote =	{Keywords: Non-planar Orthogonal Drawings, SAT Solver, Experimental Comparison}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.4

pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized Consensus Layer

Authors: Orestis Alpos, Bernardo David, Jakov Mitrovski, Odysseas Sofikitis, and Dionysis Zindros

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

This work addresses the inherent issues of high latency in blockchains and low scalability in traditional consensus protocols. We present pod, a novel notion of consensus whose first priority is to achieve the physically-optimal latency of 2δ, or one round-trip, i.e., requiring only one network trip (duration δ) for writing a transaction and one for reading it. To accomplish this, we first eliminate inter-replica communication. Instead, clients send transactions directly to all replicas, which independently process transactions and append them to local logs. Replicas assign a timestamp and a sequence number to each transaction in their logs, allowing clients to extract valuable metadata about the transactions and the system state. Later on, clients retrieve these logs and extract transactions (and associated metadata) from them. Necessarily, this construction achieves weaker properties than a total-order broadcast protocol, due to existing lower bounds. Our work models the primitive of pod and defines its security properties. We then show pod-core, a protocol that satisfies properties such as transaction confirmation within 2δ, censorship resistance against Byzantine replicas, and accountability for safety violations. We show that single-shot auctions can be realized using the pod notion and observe that it is also sufficient for other popular applications.

Cite as

Orestis Alpos, Bernardo David, Jakov Mitrovski, Odysseas Sofikitis, and Dionysis Zindros. pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized Consensus Layer. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 4:1-4:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alpos_et_al:LIPIcs.DISC.2025.4,
  author =	{Alpos, Orestis and David, Bernardo and Mitrovski, Jakov and Sofikitis, Odysseas and Zindros, Dionysis},
  title =	{{pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized Consensus Layer}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{4:1--4:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.4},
  URN =		{urn:nbn:de:0030-drops-248219},
  doi =		{10.4230/LIPIcs.DISC.2025.4},
  annote =	{Keywords: consensus, censorship resistance, accountability, auctions}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.42

Kudzu: Fast and Simple High-Throughput BFT

Authors: Victor Shoup, Jakub Sliwinski, and Yann Vonlanthen

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

We present Kudzu, a high-throughput atomic broadcast protocol with an integrated fast path. Our contribution is based on the combination of two lines of work. Firstly, our protocol achieves finality in just two rounds of communication if all but p out of n = 3f + 2p + 1 participating replicas behave correctly, where f is the number of Byzantine faults that are tolerated. Due to the seamless integration of the fast path, even in the presence of more than p faults, our protocol maintains state-of-the-art characteristics. Secondly, our protocol utilizes the bandwidth of participating replicas in a balanced way, alleviating the bottleneck at the leader, and thus enabling high throughput. This is achieved by disseminating blocks using erasure codes. Despite combining a novel set of advantages, Kudzu is remarkably simple: intricacies such as "progress certificates", complex view changes, and speculative execution are avoided.

Cite as

Victor Shoup, Jakub Sliwinski, and Yann Vonlanthen. Kudzu: Fast and Simple High-Throughput BFT. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{shoup_et_al:LIPIcs.DISC.2025.42,
  author =	{Shoup, Victor and Sliwinski, Jakub and Vonlanthen, Yann},
  title =	{{Kudzu: Fast and Simple High-Throughput BFT}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{42:1--42:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.42},
  URN =		{urn:nbn:de:0030-drops-248597},
  doi =		{10.4230/LIPIcs.DISC.2025.42},
  annote =	{Keywords: Consensus, Blockchain, Byzantine Fault Tolerance, Fast Path, State Machine Replication}
}

Document

DOI: 10.4230/LIPIcs.AFT.2025.18

From Permissioned to Proof-of-Stake Consensus

Authors: Jovan Komatovic, Andrew Lewis-Pye, Joachim Neu, Tim Roughgarden, and Ertem Nusret Tas

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract

This paper presents the first generic compiler that transforms any permissioned consensus protocol into a proof-of-stake permissionless consensus protocol. For each of the following properties, if the initial permissioned protocol satisfies that property in the partially synchronous setting, the consequent proof-of-stake protocol also satisfies that property in the partially synchronous and quasi-permissionless setting (with the same fault-tolerance): consistency; liveness; optimistic responsiveness; every composable log-specific property; and message complexity of a given order. Moreover, our transformation ensures that the output protocol satisfies accountability (identifying culprits in the event of a consistency violation), whether or not the original permissioned protocol satisfied it.

Cite as

Jovan Komatovic, Andrew Lewis-Pye, Joachim Neu, Tim Roughgarden, and Ertem Nusret Tas. From Permissioned to Proof-of-Stake Consensus. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 18:1-18:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{komatovic_et_al:LIPIcs.AFT.2025.18,
  author =	{Komatovic, Jovan and Lewis-Pye, Andrew and Neu, Joachim and Roughgarden, Tim and Tas, Ertem Nusret},
  title =	{{From Permissioned to Proof-of-Stake Consensus}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{18:1--18:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.18},
  URN =		{urn:nbn:de:0030-drops-247373},
  doi =		{10.4230/LIPIcs.AFT.2025.18},
  annote =	{Keywords: Permissioned Consensus, Proof-of-Stake, generic Compiler, Blockchain}
}

Document

DOI: 10.4230/LIPIcs.AFT.2025.19

Two-Tier Black-Box Blockchains and Application to Instant Layer-1 Payments

Authors: Michele Ciampi, Yun Lu, Rafail Ostrovsky, and Vassilis Zikas

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract

Common blockchain protocols are monolithic, i.e., their security relies on a single assumption, e.g., honest majority of hashing power (Bitcoin) or stake (Cardano, Algorand, Ethereum). In contrast, so-called optimistic approaches (Thunderella, Meshcash) rely on a combination of assumptions to achieve faster transaction liveness. We revisit, redesign, and augment the optimistic paradigm to a tiered approach. Our design assumes a primary (Tier 1) and a secondary (Tier 2, also referred to as fallback) blockchain, and achieves full security also in a tiered fashion: If the assumption underpinning the primary chain holds, then we guarantee safety, liveness and censorship resistance, irrespectively of the status of the fallback chain. And even if the primary assumption fails, all security properties are still satisfied (albeit with a temporary slow down) provided the fallback assumption holds. To our knowledge, no existing optimistic or tiered approach preserves both safety and liveness when any one of its underlying blockchain (assumptions) fails. The above is achieved by a new detection-and-recovery mechanism that links the two blockchains, so that any violation of safety, liveness, or censorship resistance on the (faster) primary blockchain is temporary - it is swiftly detected and recovered on the secondary chain - and thus cannot result in a persistent fork or halt of the blockchain ledger. We instantiate the above paradigm using a primary chain based on proof of reputation (PoR) and a fallback chain based on proof of stake (PoS). Our construction uses the PoR and PoS blockchains in a mostly black-box manner - where rather than assuming a concrete construction we distil abstract properties on the two blockchains that are sufficient for applying our tiered methodology. In fact, choosing reputation as the resource of the primary chain opens the door to an incentive mechanism - which we devise and analyze - that tokenizes reputation in order to deter cheating and boost participation (on both the primary/PoR and the fallback/PoS blockchain). As we demonstrate, such tokenization in combination with interpreting reputation as a built-in system-wide credit score, allows for embedding in our two-tiered methodology a novel mechanism which provides collateral-free, multi-use payment-channel-like functionality where payments can be instantly confirmed.

Cite as

Michele Ciampi, Yun Lu, Rafail Ostrovsky, and Vassilis Zikas. Two-Tier Black-Box Blockchains and Application to Instant Layer-1 Payments. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ciampi_et_al:LIPIcs.AFT.2025.19,
  author =	{Ciampi, Michele and Lu, Yun and Ostrovsky, Rafail and Zikas, Vassilis},
  title =	{{Two-Tier Black-Box Blockchains and Application to Instant Layer-1 Payments}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.19},
  URN =		{urn:nbn:de:0030-drops-247380},
  doi =		{10.4230/LIPIcs.AFT.2025.19},
  annote =	{Keywords: Fault tolerant blockchain, instantly confirmed payments}
}

Document

DOI: 10.4230/LIPIcs.AFT.2025.15

Beyond Optimal Fault-Tolerance

Authors: Andrew Lewis-Pye and Tim Roughgarden

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract

One of the most basic properties of a consensus protocol is its fault-tolerance - the maximum fraction of faulty participants that the protocol can tolerate without losing fundamental guarantees such as safety and liveness. Because of its importance, the optimal fault-tolerance achievable by any protocol has been characterized in a wide range of settings. For example, for state machine replication (SMR) protocols operating in the partially synchronous setting, it is possible to simultaneously guarantee consistency against α-bounded adversaries (i.e., adversaries that control less than an α fraction of the participants) and liveness against β-bounded adversaries if and only if α + 2β ≤ 1. This paper characterizes to what extent "better-than-optimal" fault-tolerance guarantees are possible for SMR protocols when the standard consistency requirement is relaxed to allow a bounded number r of consistency violations, each potentially leading to the rollback of recently finalized transactions. We prove that bounded rollback is impossible without additional timing assumptions and investigate protocols that tolerate and recover from consistency violations whenever message delays around the time of an attack are bounded by a parameter Δ^* (which may be arbitrarily larger than the parameter Δ that bounds post-GST message delays in the partially synchronous model). Here, a protocol’s fault-tolerance can be a non-constant function of r, and we prove, for each r, matching upper and lower bounds on the optimal "recoverable fault-tolerance" achievable by any SMR protocol. For example, for protocols that guarantee liveness against 1/3-bounded adversaries in the partially synchronous setting, a 5/9-bounded adversary can always cause one consistency violation but not two, and a 2/3-bounded adversary can always cause two consistency violations but not three. Our positive results are achieved through a generic "recovery procedure" that can be grafted on to any accountable SMR protocol and restores consistency following a violation while rolling back only transactions that were finalized in the previous 2Δ^* timesteps.

Cite as

Andrew Lewis-Pye and Tim Roughgarden. Beyond Optimal Fault-Tolerance. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lewispye_et_al:LIPIcs.AFT.2025.15,
  author =	{Lewis-Pye, Andrew and Roughgarden, Tim},
  title =	{{Beyond Optimal Fault-Tolerance}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{15:1--15:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.15},
  URN =		{urn:nbn:de:0030-drops-247341},
  doi =		{10.4230/LIPIcs.AFT.2025.15},
  annote =	{Keywords: Distributed computing, consensus, recovery}
}

47 Search Results for "Tse, David"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message