Search Results

Documents authored by Alpturer, Kaya

Document
DOI: 10.4230/LIPIcs.DISC.2024.2
A Knowledge-Based Analysis of Intersection Protocols

Authors: Kaya Alpturer, Joseph Y. Halpern, and Ron van der Meyden

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
The increasing wireless communication capabilities of vehicles creates opportunities for more efficient intersection management strategies. One promising approach is the replacement of traffic lights with a system wherein vehicles run protocols among themselves to determine right of way. In this paper, we define the intersection problem to model this scenario abstractly, without any assumptions on the specific structure of the intersection or a bound on the number of vehicles. Protocols solving the intersection problem must guarantee safety (no collisions) and liveness (every vehicle eventually goes through). In addition, we would like these protocols to satisfy various optimality criteria, some of which turn out to be achievable only in a subset of the contexts. In particular, we show a partial equivalence between eliminating unnecessary waiting, a criterion of interest in the distributed mutual-exclusion literature, and a notion of optimality that we define called lexicographical optimality. We then introduce a framework to design protocols for the intersection problem by converting an intersection policy, which is based on a global view of the intersection, to a protocol that can be run by the vehicles through the use of knowledge-based programs. Our protocols are shown to guarantee safety and liveness while also being optimal under sufficient conditions on the context. Finally, we investigate protocols in the presence of faulty vehicles that experience communication failures and older vehicles with limited communication capabilities. We show that intersection protocols can be made safe, live and optimal even in the presence of faulty behavior.
Cite as

Kaya Alpturer, Joseph Y. Halpern, and Ron van der Meyden. A Knowledge-Based Analysis of Intersection Protocols. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{alpturer_et_al:LIPIcs.DISC.2024.2,
  author =	{Alpturer, Kaya and Halpern, Joseph Y. and van der Meyden, Ron},
  title =	{{A Knowledge-Based Analysis of Intersection Protocols}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{2:1--2:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.2},
  URN =		{urn:nbn:de:0030-drops-212291},
  doi =		{10.4230/LIPIcs.DISC.2024.2},
  annote =	{Keywords: Intersection management, Autonomous vehicles, Distributed algorithms, Epistemic logic, Fault tolerance}
}
Document
DOI: 10.4230/LIPIcs.AFT.2024.10
Optimal RANDAO Manipulation in Ethereum

Authors: Kaya Alpturer and S. Matthew Weinberg

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract
It is well-known that RANDAO manipulation is possible in Ethereum if an adversary controls the proposers assigned to the last slots in an epoch. We provide a methodology to compute, for any fraction α of stake owned by an adversary, the maximum fraction f(α) of rounds that a strategic adversary can propose. We further implement our methodology and compute f(⋅) for all α. For example, we conclude that an optimal strategic participant with 5% of the stake can propose a 5.048% fraction of rounds, 10% of the stake can propose a 10.19% fraction of rounds, and 20% of the stake can propose a 20.68% fraction of rounds.
Cite as

Kaya Alpturer and S. Matthew Weinberg. Optimal RANDAO Manipulation in Ethereum. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{alpturer_et_al:LIPIcs.AFT.2024.10,
  author =	{Alpturer, Kaya and Weinberg, S. Matthew},
  title =	{{Optimal RANDAO Manipulation in Ethereum}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.10},
  URN =		{urn:nbn:de:0030-drops-209467},
  doi =		{10.4230/LIPIcs.AFT.2024.10},
  annote =	{Keywords: Proof of Stake, Consensus, Blockchain, Ethereum, Randomness manipulation}
}
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