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

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

Activités de recherche : Algorithmique distribuée

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
Langage d'icônes et visualisation d'ensembles : mé
Thursday 24 October 2019 - 14h30
Salle : 475 - PCRI-N
Jean-Baptiste Lamy .............................................

Matchings and related structures with Specified Co
Théorie des graphes
Thursday 17 October 2019 - 14h30
Salle : 445 - PCRI-N
Yannis Manoussakis .............................................

Conservation of structural long-range modules in R
Thursday 17 October 2019 - 14h30
Salle : 475 - PCRI-N
Vladimir Reinharz .............................................

Overcoming interference in the beeping communicati
Algorithmique distribuée
Friday 11 October 2019 - 14h30
Salle : 445 - PCRI-N
Fabien Dufoulon .............................................

Local checkability: a notion that started in the c
Algorithmique distribuée
Tuesday 08 October 2019 - 11h00
Salle : 465 - PCRI-N
Prof. Kutten Shay .............................................