DROPS

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/DagSemRep.282

Logics for Emerging Applications of Databases (Dagstuhl Seminar 00291)

Authors: Jan Chomicki, Ron van der Meyden, and Gunter Saake

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract

Cite as

Jan Chomicki, Ron van der Meyden, and Gunter Saake. Logics for Emerging Applications of Databases (Dagstuhl Seminar 00291). Dagstuhl Seminar Report 282, pp. 1-40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{chomicki_et_al:DagSemRep.282,
  author =	{Chomicki, Jan and van der Meyden, Ron and Saake, Gunter},
  title =	{{Logics for Emerging Applications of Databases (Dagstuhl Seminar 00291)}},
  pages =	{1--40},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{282},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.282},
  URN =		{urn:nbn:de:0030-drops-151664},
  doi =		{10.4230/DagSemRep.282},
}

Search Results

Documents authored by van der Meyden, Ron

A Knowledge-Based Analysis of Intersection Protocols

Abstract

Cite as

Logics for Emerging Applications of Databases (Dagstuhl Seminar 00291)

Abstract

Cite as

Thanks for your feedback!

Could not send message