WHAT CAN BE COMPUTED LOCALLY

The purpose of this paper is a study of computation that can be done l ocally in a distributed network, where ''locally'' means within time ( or distance) independent of the size of the network. Locally checkable labeling (LCL) problems are considered, where the legality of a label ing can be checked locally (e.g., coloring). The results include the f ollowing: There are nontrivial LCL problems that have local algorithms . There is a variant of the dining philosophers problem that can be so lved locally. Randomization cannot make an LCL problem local; i.e., if a problem has a local randomized algorithm then it has a local determ inistic algorithm. It is undecidable, in general, whether a given LCL has a local algorithm. However, it is decidable whether a given LCL ha s an algorithm that operates in a given lime t. Any LCL problem that h as a local algorithm has one that is order-invariant (the algorithm de pends only on the order of the processor IDs).