Skip to Main content Skip to Navigation
Conference papers

What Makes a Distributed Problem Truly Local?

Adrian Kosowski 1
1 GANG - Networks, Graphs and Algorithms
IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale, Inria de Paris
Abstract : In this talk we attempt to identify the characteristics of a task of distributed network computing, which make it easy (or hard) to solve by means of fast local algorithms. We look at specific combinatorial tasks within the LOCAL model of distributed computation, and rephrase some recent algorithmic results in a framework of constraint satisfaction. Finally, we discuss the issue of efficient computability for relaxed variants of the LOCAL model, involving the so-called non-signaling property.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-01415090
Contributor : Adrian Kosowski Connect in order to contact the contributor
Submitted on : Monday, January 2, 2017 - 5:01:57 PM
Last modification on : Friday, January 21, 2022 - 3:18:57 AM
Long-term archiving on: : Tuesday, April 4, 2017 - 12:49:53 AM

Files

inv-kosowski-hal.pdf
Files produced by the author(s)

Identifiers

Citation

Adrian Kosowski. What Makes a Distributed Problem Truly Local?. SIROCCO 2016 - 23rd International Colloquium on Structural Information and Communication Complexity, Jul 2016, Helsinki, Finland. pp.3, ⟨10.1007/978-3-319-48314-6⟩. ⟨hal-01415090⟩

Share

Metrics

Les métriques sont temporairement indisponibles