License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2022.3
URN: urn:nbn:de:0030-drops-170660
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17066/
Go to the corresponding LIPIcs Volume Portal

Rajsbaum, Sergio

Distributed Decision Problems: Concurrent Specifications Beyond Binary Relations (Invited Talk)

pdf-format:
LIPIcs-CONCUR-2022-3.pdf (1 MB)

Abstract

Much discussion exists about what is computation, but less about is a computational problem. Turing’s definition of computation was based on computing functions. When we move from sequential computing to interactive computing, discussions concentrate on computations that do not terminate, overlooking notions of distributed problems. Many models where concurrency happens have been proposed, ranging from those equivalent to a Turing machine, to those where much heated discussion has taken place, claiming that interactive models are fundamentally different from Turing machines.
It is argued here that there is no need to go all the way to non-terminating interaction, to appreciate how different distributed computation is from sequential computation. The discussion concentrates on the various ways that exist of representing a distributed decision problem. Each process of a distributed system starts with an initial private input value, and after communicating with other processes in the system, produces a local output value. An input/output relation is needed, to specify which output values are legal for a particular assignment of input values to the processes.
An overview is provided of some results that show how rich the topic of distributed decision problems can be, when asynchronous processes can fail, but mostly independent of particular models of distributed computing and their many intricate details (types of failures and of communication). We are in a world very different from that of the functions of sequential computation; moving away from the world of graphs beyond binary relations, to the world of simplicial complexes.

BibTeX - Entry

@InProceedings{rajsbaum:LIPIcs.CONCUR.2022.3,
  author =	{Rajsbaum, Sergio},
  title =	{{Distributed Decision Problems: Concurrent Specifications Beyond Binary Relations}},
  booktitle =	{33rd International Conference on Concurrency Theory (CONCUR 2022)},
  pages =	{3:1--3:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-246-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{243},
  editor =	{Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17066},
  URN =		{urn:nbn:de:0030-drops-170660},
  doi =		{10.4230/LIPIcs.CONCUR.2022.3},
  annote =	{Keywords: Distributed decision tasks, simplicial complex, linearizability, interval-linearizability, Arrow’s impossibility, Speedup theorems}
}

Keywords: Distributed decision tasks, simplicial complex, linearizability, interval-linearizability, Arrow’s impossibility, Speedup theorems
Collection: 33rd International Conference on Concurrency Theory (CONCUR 2022)
Issue Date: 2022
Date of publication: 06.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI