Search Results

Documents authored by de Haan, Ronald

Document
DOI: 10.4230/OASIcs.Tokenomics.2020.5
Decentralization in Open Quorum Systems: Limitative Results for Ripple and Stellar

Authors: Andrea Bracciali, Davide Grossi, and Ronald de Haan

Published in: OASIcs, Volume 82, 2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020)

Abstract
Decentralisation is one of the promises introduced by blockchain technologies: fair and secure interaction amongst peers with no dominant positions, single points of failure or censorship. Decentralisation, however, appears difficult to be formally defined, possibly a continuum property of systems that can be more or less decentralised, or can tend to decentralisation in their lifetime. In this paper we focus on decentralisation in quorum-based approaches to open (permissionless) consensus as illustrated in influential protocols such as the Ripple and Stellar protocols. Drawing from game theory and computational complexity, we establish limiting results concerning the decentralisation vs. safety trade-off in Ripple and Stellar, and we propose a novel methodology to formalise and quantitatively analyse decentralisation in this type of blockchains.
Cite as

Andrea Bracciali, Davide Grossi, and Ronald de Haan. Decentralization in Open Quorum Systems: Limitative Results for Ripple and Stellar. In 2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020). Open Access Series in Informatics (OASIcs), Volume 82, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bracciali_et_al:OASIcs.Tokenomics.2020.5,
  author =	{Bracciali, Andrea and Grossi, Davide and de Haan, Ronald},
  title =	{{Decentralization in Open Quorum Systems: Limitative Results for Ripple and Stellar}},
  booktitle =	{2nd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2020)},
  pages =	{5:1--5:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-157-3},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{82},
  editor =	{Anceaume, Emmanuelle and Bisi\`{e}re, Christophe and Bouvard, Matthieu and Bramas, Quentin and Casamatta, Catherine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2020.5},
  URN =		{urn:nbn:de:0030-drops-135277},
  doi =		{10.4230/OASIcs.Tokenomics.2020.5},
  annote =	{Keywords: Blockchain, decentralization, game theory, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.17
Restricted Power - Computational Complexity Results for Strategic Defense Games

Authors: Ronald de Haan and Petra Wolf

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
We study the game Greedy Spiders, a two-player strategic defense game, on planar graphs and show PSPACE-completeness for the problem of deciding whether one player has a winning strategy for a given instance of the game. We also generalize our results in metatheorems, which consider a large set of strategic defense games. We achieve more detailed complexity results by restricting the possible strategies of one of the players, which leads us to Sigma^p_2- and Pi^p_2-hardness results.
Cite as

Ronald de Haan and Petra Wolf. Restricted Power - Computational Complexity Results for Strategic Defense Games. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dehaan_et_al:LIPIcs.FUN.2018.17,
  author =	{de Haan, Ronald and Wolf, Petra},
  title =	{{Restricted Power - Computational Complexity Results for Strategic Defense Games}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.17},
  URN =		{urn:nbn:de:0030-drops-88082},
  doi =		{10.4230/LIPIcs.FUN.2018.17},
  annote =	{Keywords: Computational complexity, generalized games, metatheorems}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.42
On Existential MSO and its Relation to ETH

Authors: Robert Ganian, Ronald de Haan, Iyad Kanj, and Stefan Szeider

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
Impagliazzo et al. proposed a framework, based on the logic fragment defining the complexity class SNP, to identify problems that are equivalent to k-CNF-Sat modulo subexponential-time reducibility (serf-reducibility). The subexponential-time solvability of any of these problems implies the failure of the Exponential Time Hypothesis (ETH). In this paper, we extend the framework of Impagliazzo et al., and identify a larger set of problems that are equivalent to k-CNF-Sat modulo serf-reducibility. We propose a complexity class, referred to as Linear Monadic NP, that consists of all problems expressible in existential monadic second order logic whose expressions have a linear measure in terms of a complexity parameter, which is usually the universe size of the problem. This research direction can be traced back to Fagin's celebrated theorem stating that NP coincides with the class of problems expressible in existential second order logic. Monadic NP, a well-studied class in the literature, is the restriction of the aforementioned logic fragment to existential monadic second order logic. The proposed class Linear Monadic NP is then the restriction of Monadic NP to problems whose expressions have linear measure in the complexity parameter. We show that Linear Monadic NP includes many natural complete problems such as the satisfiability of linear-size circuits, dominating set, independent dominating set, and perfect code. Therefore, for any of these problems, its subexponential-time solvability is equivalent to the failure of ETH. We prove, using logic games, that the aforementioned problems are inexpressible in the monadic fragment of SNP, and hence, are not captured by the framework of Impagliazzo et al. Finally, we show that Feedback Vertex Set is inexpressible in existential monadic second order logic, and hence is not in Linear Monadic NP, and investigate the existence of certain reductions between Feedback Vertex Set (and variants of it) and 3-CNF-Sat.
Cite as

Robert Ganian, Ronald de Haan, Iyad Kanj, and Stefan Szeider. On Existential MSO and its Relation to ETH. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.MFCS.2016.42,
  author =	{Ganian, Robert and de Haan, Ronald and Kanj, Iyad and Szeider, Stefan},
  title =	{{On Existential MSO and its Relation to ETH}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.42},
  URN =		{urn:nbn:de:0030-drops-64556},
  doi =		{10.4230/LIPIcs.MFCS.2016.42},
  annote =	{Keywords: exponential time hypothesis (ETH), monadic second order logic, subexponential time complexity, serf-reducibility, logic games}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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