Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) Parallel Systems
Local checkability: a notion that started in the context of self-stabilization and its wider impacts
Prof. Kutten Shay

08 October 2019, 11:00
Salle/Bat : 465/PCRI-N
Contact :

Activités de recherche : Distributed algorithms

Résumé :
In this talk, I outline the notion of local checkability and point at various ways this has proven useful. Local checking (or local verification, or local decision, or local detection, or...) and locally checkable predicates (or languages, or labeling, or ...) were suggested (by Afek, K., and Yuvan, 1990) in the context of self-stabilization. The motivation was the "easy" detection that program malfunctions so that it can be restarted. It was contrasted with the "costly" (i.e. global) checking suggested by Katz and Perry.

It was pointed out that this notion also resembles "easy" checking (or decision, or ...), i.e. polynomial vs. "costly" computing. Indeed, the use of this notion has spread beyond self-stabilization to various fields such as (distributed) complexity theory, distributed testing and peer to peer computing.

Pour en savoir plus :
Séminaires
Programming computing media (reporté)
Combinatorics
Friday 18 September 2020 - 14:30
Salle : 445 - PCRI-N
Frédéric Gruau .............................................

forum-dev Continuous Integration
Friday 05 June 2020 - 10:00
Salle : 0 - 650
Erik Bray .............................................

Large-scale Spectral Clustering for GPU-based Plat
High-performance computing
Tuesday 24 March 2020 - 10:30
Salle : 465 - PCRI-N
Guanlin He .............................................

Recherche Opérationnelle à Google
Stochastic Combinatorial Optimization
Thursday 12 March 2020 - 14:30
Salle : 445 - PCRI-N
Laurent Perron .............................................

Forum dev-LRI
Wednesday 05 February 2020 - 14:00
Salle : 455 - PCRI-N
Erik Bray .............................................