|When:||Thursday, 26 September 2019, 18:30–19:50|
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.