1 Search Results for "Liu, Shihao"

Document
DOI: 10.4230/LIPIcs.OPODIS.2022.22
The Impossibility of Approximate Agreement on a Larger Class of Graphs

Authors: Shihao Liu

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Approximate agreement is a variant of consensus in which processes receive input values from a domain and must output values in that domain that are sufficiently close to one another. We study the problem when the input domain is the vertex set of a connected graph. In asynchronous systems where processes communicate using shared registers, there are wait-free approximate agreement algorithms when the graph is a path or a tree, but not when the graph is a cycle of length at least 4. For many graphs, it is unknown whether a wait-free solution for approximate agreement exists. We introduce a set of impossibility conditions and prove that approximate agreement on graphs satisfying these conditions cannot be solved in a wait-free manner. In particular, the graphs of all triangulated d-dimensional spheres that are not cliques, satisfy these conditions. The vertices and edges of an octahedron is an example of such a graph. We also present a family of reductions from approximate agreement on one graph to another graph. This allows us to extend known impossibility results to even more graphs.
Cite as

Shihao Liu. The Impossibility of Approximate Agreement on a Larger Class of Graphs. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.OPODIS.2022.22,
  author =	{Liu, Shihao},
  title =	{{The Impossibility of Approximate Agreement on a Larger Class of Graphs}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.22},
  URN =		{urn:nbn:de:0030-drops-176420},
  doi =		{10.4230/LIPIcs.OPODIS.2022.22},
  annote =	{Keywords: Approximate agreement on graph, wait-free solvability, triangulated sphere}
}
  • Refine by Author
  • 1 Liu, Shihao

  • Refine by Classification
  • 1 Theory of computation → Computability
  • 1 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 1 Approximate agreement on graph
  • 1 triangulated sphere
  • 1 wait-free solvability

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

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