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 nonterminating 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:13:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772464},
ISSN = {18688969},
year = {2022},
volume = {243},
editor = {Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17066},
URN = {urn:nbn:de:0030drops170660},
doi = {10.4230/LIPIcs.CONCUR.2022.3},
annote = {Keywords: Distributed decision tasks, simplicial complex, linearizability, intervallinearizability, Arrow’s impossibility, Speedup theorems}
}
Keywords: 

Distributed decision tasks, simplicial complex, linearizability, intervallinearizability, Arrow’s impossibility, Speedup theorems 
Collection: 

33rd International Conference on Concurrency Theory (CONCUR 2022) 
Issue Date: 

2022 
Date of publication: 

06.09.2022 