What Makes a Distributed Problem Truly Local?

Adrian Kosowski 1
1 GANG - Networks, Graphs and Algorithms
Inria de Paris, IRIF - Institut de Recherche en Informatique Fondamentale
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.
Type de document :
Communication dans un congrès
Jukka Suomela SIROCCO 2016 - 23rd International Colloquium on Structural Information and Communication Complexity, Jul 2016, Helsinki, Finland. Springer, 9988 pp.3, Lecture Notes in Computer Science. 〈10.1007/978-3-319-48314-6〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01415090
Contributeur : Adrian Kosowski <>
Soumis le : lundi 2 janvier 2017 - 17:01:57
Dernière modification le : jeudi 15 novembre 2018 - 20:27:45
Document(s) archivé(s) le : mardi 4 avril 2017 - 00:49:53

Fichiers

inv-kosowski-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Adrian Kosowski. What Makes a Distributed Problem Truly Local?. Jukka Suomela SIROCCO 2016 - 23rd International Colloquium on Structural Information and Communication Complexity, Jul 2016, Helsinki, Finland. Springer, 9988 pp.3, Lecture Notes in Computer Science. 〈10.1007/978-3-319-48314-6〉. 〈hal-01415090〉

Partager

Métriques

Consultations de la notice

233

Téléchargements de fichiers

29