38 Search Results for "Rodrigues, David"

Document
DOI: 10.4230/LIPIcs.CPM.2026.14
Hardness Results on Characteristics for Elastic-Degenerate Strings

Authors: Dominik Köppl and Jannik Olbrich

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
Generalizations of plain strings have been proposed as a compact way to represent a collection of nearly identical sequences or to express uncertainty at specific text positions by enumerating all possibilities. While a plain string stores a character at each of its positions, generalizations consider a set of characters (indeterminate strings), a set of strings of equal length (generalized degenerate strings, or shortly GD strings), or a set of strings of arbitrary lengths (elastic-degenerate strings, or shortly ED strings). These generalizations are of importance to compactly represent such type of data, and find applications in bioinformatics for representing and maintaining a set of genetic sequences of the same taxonomy or a multiple sequence alignment. To be of use, attention has been drawn to answering various query types such as pattern matching or measuring similarity of ED strings by generalizing techniques known to plain strings. However, for some types of queries, it has been shown that a generalization of a polynomial-time solvable query on classic strings becomes NP-hard on ED strings, e.g. [Russo et al., 2022]. In that light, we wonder about other types of queries that are of particular interest to bioinformatics: unique substrings, absent words, anti-powers, longest previous factors, and Lempel-Ziv-like compression schemes. While we obtain a polynomial time algorithm for a variation of longest previous factors, we show that all other problems are NP-hard to compute, some of them even under the restriction that the input can be modeled as an indeterminate or GD string.
Cite as

Dominik Köppl and Jannik Olbrich. Hardness Results on Characteristics for Elastic-Degenerate Strings. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{koppl_et_al:LIPIcs.CPM.2026.14,
  author =	{K\"{o}ppl, Dominik and Olbrich, Jannik},
  title =	{{Hardness Results on Characteristics for Elastic-Degenerate Strings}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{14:1--14:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.14},
  URN =		{urn:nbn:de:0030-drops-259409},
  doi =		{10.4230/LIPIcs.CPM.2026.14},
  annote =	{Keywords: Elastic-degenerate strings, NP-hardness, longest common factor, minimal unique substring, minimal absent word, anti-power, longest previous factor}
}
Document
DOI: 10.4230/OASIcs.FMBC.2026.3
Isabelle/EVM: A Novel Formalization of the EVM in Isabelle/HOL

Authors: Ashley Card and Diego Marmsoler

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

Abstract
Smart contracts deployed on the Ethereum blockchain execute on the Ethereum Virtual Machine (EVM) and handle financial operations such as payments, asset transfers, and auctions. Given the high value they control, correctness in these contracts is critical, as errors and vulnerabilities have led to losses totalling hundreds of millions of dollars. To address this problem, we develop a novel formalization of the EVM. Compared to existing formalizations, our formalization is in Isabelle/HOL, covers all current EVM opcodes, and formalizes cross-contract execution. Thus, it allows us to express properties which are out of scope for other formalizations. To allow for the execution of our formalization, we implement a code generator, allowing it to be exported as a stand-alone Haskell program. We then validate the semantics by executing νmprint{25000} test cases from the official Ethereum test suite. Our formalization can be used to verify concrete smart contracts but also to reason about the correctness of tools and techniques which manipulate bytecode, such as compilers or optimizers.
Cite as

Ashley Card and Diego Marmsoler. Isabelle/EVM: A Novel Formalization of the EVM in Isabelle/HOL. In 7th International Workshop on Formal Methods for Blockchains (FMBC 2026). Open Access Series in Informatics (OASIcs), Volume 142, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{card_et_al:OASIcs.FMBC.2026.3,
  author =	{Card, Ashley and Marmsoler, Diego},
  title =	{{Isabelle/EVM: A Novel Formalization of the EVM in Isabelle/HOL}},
  booktitle =	{7th International Workshop on Formal Methods for Blockchains (FMBC 2026)},
  pages =	{3:1--3:16},
  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.3},
  URN =		{urn:nbn:de:0030-drops-257005},
  doi =		{10.4230/OASIcs.FMBC.2026.3},
  annote =	{Keywords: Ethereum Virtual Machine, Isabelle/HOL, Smart Contracts}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.17
Don’t Get Caught, Keep Your Onions in a Vault

Authors: Humza Ikram, Rumaisa Habib, Muaz Ali, and Zartash Afzal Uzmi

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

Abstract
When web applications wish to operate anonymously, they routinely host themselves as "Hidden Services" in the Tor network. However, these services are frequently threatened by deanonymization attacks, whereby their IP address and location may be inferred by the authorities. We present VaulTor, a novel architecture for the Tor network that ensures an extra layer of security for the Hidden Services against deanonymization attacks. In this new architecture, a volunteer (vault) is incentivized to host the web application content on behalf of the Hidden Service. The vault runs the hosted application in a Trusted Execution Environment (TEE) and becomes the point of contact for interested clients. This setup can substantially reduce the uptime requirement of the original Hidden Service provider, thereby significantly decreasing the chance of deanonymization attacks against them. Using a vault node in place of the hidden service node does not cause any noticeable performance degradation when accessing the hosted content.
Cite as

Humza Ikram, Rumaisa Habib, Muaz Ali, and Zartash Afzal Uzmi. Don’t Get Caught, Keep Your Onions in a Vault. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 17:1-17:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ikram_et_al:OASIcs.NINeS.2026.17,
  author =	{Ikram, Humza and Habib, Rumaisa and Ali, Muaz and Uzmi, Zartash Afzal},
  title =	{{Don’t Get Caught, Keep Your Onions in a Vault}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{17:1--17:24},
  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.17},
  URN =		{urn:nbn:de:0030-drops-256027},
  doi =		{10.4230/OASIcs.NINeS.2026.17},
  annote =	{Keywords: Tor, anonymity, Hidden Services, Trusted Execution Environments}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.3
Limix: Limiting Lamport Exposure to Distant Failures in Globally-Managed Distributed Systems

Authors: Cristina Băsescu, Georgia Fragkouli, Enis Ceyhun Alp, Michael F. Nowlan, Jose M. Faleiro, Gaylor Bosson, Kelong Cong, Pierluca Borsò-Tan, Vero Estrada-Galiñanes, and Bryan Ford

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

Abstract
Globalized computing infrastructures offer the convenience and elasticity of globally managed objects and services, but lack the resilience to distant failures that localized infrastructures such as private clouds provide. Providing both global management and resilience to distant failures, however, poses a fundamental problem for configuration services: How to discover a possibly migratory, strongly-consistent service/object in a globalized infrastructure without dependencies on globalized state? Limix is the first metadata configuration service that addresses this problem. With Limix, global strongly-consistent data-plane services and objects are insulated from remote gray failures by ensuring that the definitive, strongly-consistent metadata for any object is always confined to the same region as the object itself. Limix guarantees availability bounds: any user can continue accessing any strongly consistent object that matters to the user located at distance Δ away, insulated from failures outside a small multiple of Δ. We built a Limix metadata service based on the key-value interface of CockroachDB. Our experiments on Internet-like networks and on AWS, using realistic trace-driven workloads, show that Limix enables global management and significantly improves availability over the state-of-the-art.
Cite as

Cristina Băsescu, Georgia Fragkouli, Enis Ceyhun Alp, Michael F. Nowlan, Jose M. Faleiro, Gaylor Bosson, Kelong Cong, Pierluca Borsò-Tan, Vero Estrada-Galiñanes, and Bryan Ford. Limix: Limiting Lamport Exposure to Distant Failures in Globally-Managed Distributed Systems. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 3:1-3:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{basescu_et_al:OASIcs.NINeS.2026.3,
  author =	{B\u{a}sescu, Cristina and Fragkouli, Georgia and Alp, Enis Ceyhun and Nowlan, Michael F. and Faleiro, Jose M. and Bosson, Gaylor and Cong, Kelong and Bors\`{o}-Tan, Pierluca and Estrada-Gali\~{n}anes, Vero and Ford, Bryan},
  title =	{{Limix: Limiting Lamport Exposure to Distant Failures in Globally-Managed Distributed Systems}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{3:1--3:29},
  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.3},
  URN =		{urn:nbn:de:0030-drops-255880},
  doi =		{10.4230/OASIcs.NINeS.2026.3},
  annote =	{Keywords: Distributed systems, Availability, Fault tolerance, Strong-consistency, Coordination systems, Lamport exposure}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.8
Weaker Assumptions for Asymmetric Trust

Authors: Ignacio Amores-Sesar, Christian Cachin, Simon Holmgaard Kamp, and Juan Villacis

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

Abstract
In distributed systems with asymmetric trust, each participant is free to make its own trust assumptions about others, captured by an asymmetric quorum system. This contrasts with ordinary, symmetric quorum systems and threshold models, where trust assumptions are uniformly shared among participants. Fundamental problems like reliable broadcast and consensus are unsolvable in the asymmetric model if quorum systems satisfy only the classical properties of consistency and availability. Existing approaches overcome this by introducing stronger assumptions. We show that some of these assumptions are overly restrictive, so much so that they effectively eliminate the benefits of asymmetric trust. To address this, we propose a new approach to characterize asymmetric problems and, building upon it, present algorithms for reliable broadcast and consensus that require weaker assumptions than previous solutions. Our methods are general and can be extended to other core problems in systems with asymmetric trust.
Cite as

Ignacio Amores-Sesar, Christian Cachin, Simon Holmgaard Kamp, and Juan Villacis. Weaker Assumptions for Asymmetric Trust. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.OPODIS.2025.8,
  author =	{Amores-Sesar, Ignacio and Cachin, Christian and Kamp, Simon Holmgaard and Villacis, Juan},
  title =	{{Weaker Assumptions for Asymmetric Trust}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{8:1--8:18},
  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.8},
  URN =		{urn:nbn:de:0030-drops-251812},
  doi =		{10.4230/LIPIcs.OPODIS.2025.8},
  annote =	{Keywords: Asymmetric Trust, Quorum Systems, Reliable Broadcast, Consensus}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.11
Formalizing Rollback Netcodes for Robust and Real-Time Client-Server Architectures

Authors: Yérom-David Bromberg, Jérémie Decouchant, Manon Sourisseau, and François Taïani

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

Abstract
The rapid growth of the gaming industry has made netcodes (the part of an online game’s source code that handles networking and synchronization) a critical component of the online multiplayer experience. Among various approaches, rollback netcodes have become a popular choice for real-time games due to their ability to enhance responsiveness and player immersion. However, despite their widespread adoption, these netcodes remain susceptible to subtle latency-based attacks that can be challenging to detect. Notably, while rollback netcodes play a critical role in the gaming industry and share similarities with synchronization mechanisms in distributed systems, they have received relatively limited attention in academic research. In this work, we present a formal specification of rollback netcodes and identify key behavioral properties and requirements to strengthen their resilience against latency-based attacks that are prevalent in gaming, such as lag-switch and DDoS attacks. Our analysis allows us to explore the trade-offs between preserving immersive gameplay and ensuring security. Our findings reveal that ideal immersion requires strict assumptions about network latency, which are unattainable in adversarial environments where message delays are inevitable.
Cite as

Yérom-David Bromberg, Jérémie Decouchant, Manon Sourisseau, and François Taïani. Formalizing Rollback Netcodes for Robust and Real-Time Client-Server Architectures. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bromberg_et_al:LIPIcs.OPODIS.2025.11,
  author =	{Bromberg, Y\'{e}rom-David and Decouchant, J\'{e}r\'{e}mie and Sourisseau, Manon and Ta\"{i}ani, Fran\c{c}ois},
  title =	{{Formalizing Rollback Netcodes for Robust and Real-Time Client-Server Architectures}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{11:1--11:17},
  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.11},
  URN =		{urn:nbn:de:0030-drops-251841},
  doi =		{10.4230/LIPIcs.OPODIS.2025.11},
  annote =	{Keywords: Online Multiplayer Game, Rollback Netcode, Network Security, Latency attacks}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.33
Resolving Conflicts with Grace: Dynamically Concurrent Universality

Authors: Petr Kuznetsov and Nathan Josia Schrodt

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

Abstract
Synchronization is the major obstacle to scalability in distributed computing. Concurrent operations on the shared data engage in synchronization when they encounter a conflict, i.e., their effects depend on the order in which they are applied. Ideally, one would like to detect conflicts in a dynamic manner, i.e., adjusting to the current system state. Indeed, it is very common that two concurrent operations conflict only in some rarely occurring states. In this paper, we define the notion of dynamic concurrency: an operation employs strong synchronization primitives only if it has to arbitrate with concurrent operations, given the current system state. We then present a dynamically concurrent universal construction.
Cite as

Petr Kuznetsov and Nathan Josia Schrodt. Resolving Conflicts with Grace: Dynamically Concurrent Universality. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 33:1-33:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kuznetsov_et_al:LIPIcs.OPODIS.2025.33,
  author =	{Kuznetsov, Petr and Schrodt, Nathan Josia},
  title =	{{Resolving Conflicts with Grace: Dynamically Concurrent Universality}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{33:1--33:29},
  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.33},
  URN =		{urn:nbn:de:0030-drops-252068},
  doi =		{10.4230/LIPIcs.OPODIS.2025.33},
  annote =	{Keywords: Universal Construction, Consensus, Dynamic Concurrency}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.39
TEE Is Not a Healer: Rollback-Resistant Reliable Storage

Authors: Sadegh Keshavarzi, Gregory Chockler, and Alexey Gotsman

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

Abstract
Recent advances in secure hardware technologies, such as Intel SGX or ARM TrustZone, offer an opportunity to substantially reduce the costs of Byzantine fault-tolerance by placing the program code and state within a secure enclave known as a Trusted Execution Environment (TEE). However, the protection offered by a TEE only applies during program execution. Once power is switched off, the non-volatile portion of the program state becomes vulnerable to rollback attacks wherein it is undetectably reverted to an older version. In this paper we consider the problem of implementing reliable read/write registers out of failure-prone replicas subject to state rollbacks. To this end, we introduce a new unified model that captures multiple failure types that can affect a TEE-based system and establish tight bounds on the fault-tolerance of register constructions in this model. We consider both the static case, where failure thresholds hold throughout the entire execution, and the dynamic case, where any number of replicas can roll back, provided these failures do not occur too often. Our dynamic register emulation algorithm, TEE-Rex , provides the first correct implementation of a distributed state recovery procedure that requires neither durable storage nor specialized hardware, such as trusted monotonic counters.
Cite as

Sadegh Keshavarzi, Gregory Chockler, and Alexey Gotsman. TEE Is Not a Healer: Rollback-Resistant Reliable Storage. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{keshavarzi_et_al:LIPIcs.DISC.2025.39,
  author =	{Keshavarzi, Sadegh and Chockler, Gregory and Gotsman, Alexey},
  title =	{{TEE Is Not a Healer: Rollback-Resistant Reliable Storage}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{39:1--39:18},
  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.39},
  URN =		{urn:nbn:de:0030-drops-248560},
  doi =		{10.4230/LIPIcs.DISC.2025.39},
  annote =	{Keywords: Trusted execution environments, fault tolerance, crash recovery}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.15
Asynchronous Latency and Fast Atomic Snapshot

Authors: João Paulo Bezerra, Luciano Freitas, Petr Kuznetsov, and Matthieu Rambaud

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

Abstract
This paper introduces a novel, fast atomic-snapshot protocol for asynchronous message-passing systems. In the process of defining what "fast" means exactly, we spot a few interesting issues that arise when conventional time metrics are applied to long-lived asynchronous algorithms. We reveal some gaps in latency claims made in earlier work on snapshot algorithms, which hamper their comparative time-complexity analysis. We then come up with a new unifying time-complexity metric that captures the latency of an operation in an asynchronous, long-lived implementation. This allows us to formally grasp latency improvements of our atomic-snapshot algorithm with respect to the state-of-the-art protocols: optimal latency in fault-free runs without contention, short constant latency in fault-free runs with contention, the worst-case latency proportional to the number of active concurrent failures, and constant amortized latency.
Cite as

João Paulo Bezerra, Luciano Freitas, Petr Kuznetsov, and Matthieu Rambaud. Asynchronous Latency and Fast Atomic Snapshot. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bezerra_et_al:LIPIcs.DISC.2025.15,
  author =	{Bezerra, Jo\~{a}o Paulo and Freitas, Luciano and Kuznetsov, Petr and Rambaud, Matthieu},
  title =	{{Asynchronous Latency and Fast Atomic Snapshot}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{15:1--15:22},
  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.15},
  URN =		{urn:nbn:de:0030-drops-248326},
  doi =		{10.4230/LIPIcs.DISC.2025.15},
  annote =	{Keywords: Asynchronous systems, time complexity, atomic snapshot, crash faults}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.45
Brief Announcement: DAGs for the Masses

Authors: Michael Anoprenko, Andrei Tonkikh, Alexander Spiegelman, and Petr Kuznetsov

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

Abstract
A recent approach to building consensus protocols on top of Directed Acyclic Graphs (DAGs) shows much promise due to its simplicity and stable throughput. However, as each node in the DAG typically includes a linear number of references to the nodes in the previous round, prior DAG protocols only scale up to a certain point when the overhead of maintaining the graph becomes the bottleneck. To enable large-scale deployments of DAG-based protocols, we propose a sparse DAG architecture, where each node includes only a constant number of references to random nodes in the previous round. We present a sparse version of Bullshark - one of the most prominent DAG-based consensus protocols - and demonstrate its improved scalability. Remarkably, unlike other protocols that use random sampling to reduce communication complexity, we manage to avoid sacrificing resilience: the protocol can tolerate up to f < n/3 Byzantine faults (where n is the number of participants), same as its less scalable deterministic counterpart. The proposed "sparse" methodology can be applied to any protocol that maintains disseminated system updates and causal relations between them in a graph-like structure. Our simulations show that the considerable reduction of transmitted metadata in sparse DAGs results in more efficient network utilization and better scalability.
Cite as

Michael Anoprenko, Andrei Tonkikh, Alexander Spiegelman, and Petr Kuznetsov. Brief Announcement: DAGs for the Masses. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 45:1-45:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anoprenko_et_al:LIPIcs.DISC.2025.45,
  author =	{Anoprenko, Michael and Tonkikh, Andrei and Spiegelman, Alexander and Kuznetsov, Petr},
  title =	{{Brief Announcement: DAGs for the Masses}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{45:1--45:7},
  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.45},
  URN =		{urn:nbn:de:0030-drops-248617},
  doi =		{10.4230/LIPIcs.DISC.2025.45},
  annote =	{Keywords: Consensus, Atomic Broadcast, Byzantine Fault Tolerance, DAGs, Scalability, Sampling}
}
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.14
Optimistic Message Dissemination

Authors: Chen-Da Liu-Zhang, Christian Matt, and Søren Eller Thomsen

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

Abstract
Message dissemination is a fundamental building block in distributed systems and guarantees that any message sent eventually reaches all parties. State of the art provably secure protocols for disseminating messages have a per-party communication complexity that is linear in the inverse of the fraction of parties that are guaranteed to be honest in the worst case. Unfortunately, this per-party communication complexity arises even in cases where the actual fraction of parties that behave honestly is close to 1. In this paper, we propose an optimistic message dissemination protocol that adopts to the actual conditions in which it is deployed, with optimal worst-case per-party communication complexity. Our protocol cuts the complexity of prior provably secure protocols for 49% worst-case corruption almost in half under optimistic conditions and allows practitioners to combine efficient heuristics with secure fallback mechanisms.
Cite as

Chen-Da Liu-Zhang, Christian Matt, and Søren Eller Thomsen. Optimistic Message Dissemination. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{liuzhang_et_al:LIPIcs.AFT.2025.14,
  author =	{Liu-Zhang, Chen-Da and Matt, Christian and Thomsen, S{\o}ren Eller},
  title =	{{Optimistic Message Dissemination}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{14:1--14: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.14},
  URN =		{urn:nbn:de:0030-drops-247332},
  doi =		{10.4230/LIPIcs.AFT.2025.14},
  annote =	{Keywords: flooding, message dissemination, optimistic}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.91
Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism

Authors: Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the k-core decomposition problem, the classic peeling algorithm iteratively removes a vertex if its induced degree falls below a threshold. The sparse vector technique (SVT) is generally used to transform non-private threshold queries into private ones with only a small additive loss in accuracy. However, a naive application of SVT in the graph setting leads to an amplification of the error by a factor of n due to composition, as SVT is applied to every vertex. In this paper, we resolve this problem by formulating a novel generalized sparse vector technique which we call the Multidimensional AboveThreshold (MAT) Mechanism which generalizes SVT (applied to vectors with one dimension) to vectors with multiple dimensions. When applied to vectors with n dimensions, we solve a number of important graph problems with better bounds than previous work. Specifically, we apply our MAT mechanism to obtain a set of improved bounds for a variety of problems including k-core decomposition, densest subgraph, low out-degree ordering, and vertex coloring. We give a tight local edge differentially private (LEDP) algorithm for k-core decomposition that results in an approximation with O(ε^{-1} log n) additive error and no multiplicative error in O(n) rounds. We also give a new (2+η)-factor multiplicative, O(ε^{-1} log n) additive error algorithm in O(log² n) rounds for any constant η > 0. Both of these results are asymptotically tight against our new lower bound of Ω(log n) for any constant-factor approximation algorithm for k-core decomposition. Our new algorithms for k-core decomposition also directly lead to new algorithms for the related problems of densest subgraph and low out-degree ordering. Finally, we give novel LEDP differentially private defective coloring algorithms that use number of colors given in terms of the arboricity of the graph.
Cite as

Laxman Dhulipala, Monika Henzinger, George Z. Li, Quanquan C. Liu, A. R. Sricharan, and Leqi Zhu. Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 91:1-91:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dhulipala_et_al:LIPIcs.ESA.2025.91,
  author =	{Dhulipala, Laxman and Henzinger, Monika and Li, George Z. and Liu, Quanquan C. and Sricharan, A. R. and Zhu, Leqi},
  title =	{{Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{91:1--91:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.91},
  URN =		{urn:nbn:de:0030-drops-245601},
  doi =		{10.4230/LIPIcs.ESA.2025.91},
  annote =	{Keywords: differential privacy, abovethreshold, densest subgraph}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.5
On Planar Straight-Line Dominance Drawings

Authors: Patrizio Angelini, Michael A. Bekos, Giuseppe Di Battista, Fabrizio Frati, Luca Grilli, and Giacomo Ortali

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We study the following question, which has been considered since the 90’s: Does every st-planar graph admit a planar straight-line dominance drawing? We show concrete evidence for the difficulty of this question, by proving that, unlike upward planar straight-line drawings, planar straight-line dominance drawings with prescribed y-coordinates do not always exist and planar straight-line dominance drawings cannot always be constructed via a contract-draw-expand inductive approach. We also show several classes of st-planar graphs that always admit a planar straight-line dominance drawing. These include st-planar 3-trees in which every stacking operation introduces two edges incoming into the new vertex, st-planar graphs in which every vertex is adjacent to the sink, and st-planar graphs in which no face has the left boundary that is a single edge.
Cite as

Patrizio Angelini, Michael A. Bekos, Giuseppe Di Battista, Fabrizio Frati, Luca Grilli, and Giacomo Ortali. On Planar Straight-Line Dominance Drawings. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.WADS.2025.5,
  author =	{Angelini, Patrizio and Bekos, Michael A. and Di Battista, Giuseppe and Frati, Fabrizio and Grilli, Luca and Ortali, Giacomo},
  title =	{{On Planar Straight-Line Dominance Drawings}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.5},
  URN =		{urn:nbn:de:0030-drops-242361},
  doi =		{10.4230/LIPIcs.WADS.2025.5},
  annote =	{Keywords: st-graphs, dominance drawings, planar straight-line drawings, upward planarity}
}
Document
Research
DOI: 10.4230/OASIcs.Grossi.14
Specific Patterns Against Reference Sequences

Authors: Marie-Pierre Béal and Maxime Crochemore

Published in: OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025)

Abstract
We design alignment-free techniques for comparing a set of sequences or just a word, called a target, against another set of words, called a reference. This is done with the detection of factor patterns that distinguish the target from the reference. A target-specific factor of a target T against a reference R is then a factor w of a word in T that is not a factor of a word in R but whose proper factors of w are factors of a word in R. The strategy is based on the notion of minimal absent/forbidden words. We first address the computation of the set of target-specific factors of a target T against a reference R, where T and R are finite sets of sequences. The result is the construction of an automaton accepting the set of all considered target-specific factors. The construction algorithm runs in linear time according to the size of T ∪ R. The second result is the design of an algorithm to compute all the occurrences in a single sequence T of its target-specific factors against a reference R. The algorithm runs in real-time on the target sequence, independently of the number of occurrences of target-specific factors.
Cite as

Marie-Pierre Béal and Maxime Crochemore. Specific Patterns Against Reference Sequences. In From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 132, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beal_et_al:OASIcs.Grossi.14,
  author =	{B\'{e}al, Marie-Pierre and Crochemore, Maxime},
  title =	{{Specific Patterns Against Reference Sequences}},
  booktitle =	{From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday},
  pages =	{14:1--14:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-391-1},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{132},
  editor =	{Conte, Alessio and Marino, Andrea and Rosone, Giovanna and Vitter, Jeffrey Scott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.14},
  URN =		{urn:nbn:de:0030-drops-238130},
  doi =		{10.4230/OASIcs.Grossi.14},
  annote =	{Keywords: Specific pattern, Minimal absent word, Minimal forbidden word, Directed Acyclic Word Graph (DAWG), Suffix automaton}
}
  • Refine by Type
  • 38 Document/PDF
  • 31 Document/HTML

  • Refine by Publication Year
  • 7 2026
  • 19 2025
  • 2 2024
  • 4 2023
  • 1 2022
  • Show More...

  • Refine by Author
  • 3 Kuznetsov, Petr
  • 2 Batista, Fernando
  • 2 Bonifati, Angela
  • 2 Calbimonte, Jean-Paul
  • 2 Chen, Jiaoyan
  • Show More...

  • Refine by Series/Journal
  • 18 LIPIcs
  • 10 OASIcs
  • 1 LITES
  • 5 TGDK
  • 4 DagSemProc

  • Refine by Classification
  • 9 Theory of computation → Distributed algorithms
  • 4 Security and privacy → Distributed systems security
  • 3 Information systems → Graph-based database models
  • 2 Computing methodologies → Knowledge representation and reasoning
  • 2 Computing methodologies → Natural language processing
  • Show More...

  • Refine by Keyword
  • 3 Consensus
  • 2 Availability
  • 2 Byzantine Fault Tolerance
  • 1 Algebra of Programming
  • 1 Answer-Set Programming
  • Show More...

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