Search Results

Documents authored by Pulaj, Jonad

Document
DOI: 10.4230/LIPIcs.OPODIS.2024.8
Optimal Multilevel Slashing for Blockchains

Authors: Kenan Wood, Hammurabi Mendes, and Jonad Pulaj

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

Abstract
We present the notion of multilevel slashing, where proof-of-stake blockchain validators can obtain gradual levels of assurance that a certain block is bound to be finalized in a global consensus procedure, unless an increasing and optimally large number of Byzantine processes have their staked assets slashed - that is, deducted - due to provably incorrect behavior. Our construction is a highly parameterized generalization of combinatorial intersection systems based on finite projective spaces, with asymptotic high availability and optimal slashing properties. Even under weak conditions, we show that our construction has asymptotically optimal slashing properties with respect to message complexity and validator load; this result also illustrates a fundamental trade off between message complexity, load, and slashing. In addition, we show that any intersection system whose ground elements are disjoint subsets of nodes (e.g. "committees" in committee-based consensus protocols) has asymptotic high availability under similarly weak conditions. Finally, our multilevel construction gives the flexibility to blockchain validators to decide how many "levels" of finalization assurance they wish to obtain. This functionality can be seen either as (i) a form of an early, slashing-based block finalization; or (ii) a service to support reorg tolerance.
Cite as

Kenan Wood, Hammurabi Mendes, and Jonad Pulaj. Optimal Multilevel Slashing for Blockchains. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wood_et_al:LIPIcs.OPODIS.2024.8,
  author =	{Wood, Kenan and Mendes, Hammurabi and Pulaj, Jonad},
  title =	{{Optimal Multilevel Slashing for Blockchains}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.8},
  URN =		{urn:nbn:de:0030-drops-225445},
  doi =		{10.4230/LIPIcs.OPODIS.2024.8},
  annote =	{Keywords: Blockchains, Finality, Slashablility, Committees, Availability}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.32
Distributed Agreement in the Arrovian Framework

Authors: Kenan Wood, Hammurabi Mendes, and Jonad Pulaj

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

Abstract
Preference aggregation is a fundamental problem in voting theory, in which public input rankings of a set of alternatives (called preferences) must be aggregated into a single preference that satisfies certain soundness properties. The celebrated Arrow Impossibility Theorem is equivalent to a distributed task in a synchronous fault-free system that satisfies properties such as respecting unanimous preferences, maintaining independence of irrelevant alternatives (IIA), and non-dictatorship, along with consensus since only one preference can be decided. In this work, we study a weaker distributed task in which crash faults are introduced, IIA is not required, and the consensus property is relaxed to either k-set agreement or ε-approximate agreement using any metric on the set of preferences. In particular, we prove several novel impossibility results for both of these tasks in both synchronous and asynchronous distributed systems. We additionally show that the impossibility for our ε-approximate agreement task using the Kendall tau or Spearman footrule metrics holds under extremely weak assumptions.
Cite as

Kenan Wood, Hammurabi Mendes, and Jonad Pulaj. Distributed Agreement in the Arrovian Framework. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wood_et_al:LIPIcs.OPODIS.2024.32,
  author =	{Wood, Kenan and Mendes, Hammurabi and Pulaj, Jonad},
  title =	{{Distributed Agreement in the Arrovian Framework}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{32:1--32:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.32},
  URN =		{urn:nbn:de:0030-drops-225686},
  doi =		{10.4230/LIPIcs.OPODIS.2024.32},
  annote =	{Keywords: Approximate Agreement, Set Agreement, Preference Aggregation, Voting Theory, Impossibility}
}
Document
DOI: 10.4230/OASIcs.SCOR.2016.8
Towards the Integration of Power-Indexed Formulations in Multi-Architecture Connected Facility Location Problems for the Optimal Design of Hybrid Fiber-Wireless Access Networks

Authors: Fabio D’Andreagiovanni, Fabian Mett, and Jonad Pulaj

Published in: OASIcs, Volume 50, 5th Student Conference on Operational Research (SCOR 2016)

Abstract
Urban access networks are the external part of worldwide networks that make telecommunication services accessible to end users and represent a critical part of the infrastructures of modern cities. An important recent trend in urban access networks is the integration of fiber and wireless networks, leading to so-called fiber-wireless (Fi-Wi) networks. Fi-Wi networks get the best of both technologies, namely the high capacity offered by optical fiber networks and the mobility and ubiquity offered by wireless networks. The optimal design of fiber and wireless networks has been separately extensively studied. However, there is still a lack of mathematical models and algorithms for the integrated design problem. In this work, we propose a new Power-Indexed optimization model for the 3-architecture Connected Facility Location Problem arising in the design of urban telecommunication access networks. The new model includes additional power-indexed variables and constraints to represent the signal-to-interference formulas expressing wireless signal coverage. To solve the problem, which can prove very hard even for a state-of-the art optimization solver, we propose a new heuristic that combines a probabilistic variable fixing procedure, guided by (tight) linear relaxations, with an MIP heuristic, corresponding to an exact very large neighborhood search. Computational experiments on realistic instances show that our heuristic can find solutions of much higher quality than a state-of-the-art solver.
Cite as

Fabio D’Andreagiovanni, Fabian Mett, and Jonad Pulaj. Towards the Integration of Power-Indexed Formulations in Multi-Architecture Connected Facility Location Problems for the Optimal Design of Hybrid Fiber-Wireless Access Networks. In 5th Student Conference on Operational Research (SCOR 2016). Open Access Series in Informatics (OASIcs), Volume 50, pp. 8:1-8:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{d'andreagiovanni_et_al:OASIcs.SCOR.2016.8,
  author =	{D’Andreagiovanni, Fabio and Mett, Fabian and Pulaj, Jonad},
  title =	{{Towards the Integration of Power-Indexed Formulations in Multi-Architecture Connected Facility Location Problems for the Optimal Design of Hybrid Fiber-Wireless Access Networks}},
  booktitle =	{5th Student Conference on Operational Research (SCOR 2016)},
  pages =	{8:1--8:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-004-0},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{50},
  editor =	{Hardy, Bradley and Qazi, Abroon and Ravizza, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SCOR.2016.8},
  URN =		{urn:nbn:de:0030-drops-65209},
  doi =		{10.4230/OASIcs.SCOR.2016.8},
  annote =	{Keywords: Telecommunications Access Networks, Connected Facility Location, Mixed Integer Linear Programming, Power-Indexed Formulations, MIP Heuristics}
}
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 About DROPS Imprint Privacy Contact