  In this work, we give a unifying view of locality in four settings:
distributed algorithms, sequential greedy algorithms, dynamic algorithms, and
online algorithms. We introduce a new model of computing, called the
online-LOCAL model: the adversary reveals the nodes of the input graph one by
one, in the same way as in classical online algorithms, but for each new node
we get to see its radius-T neighborhood before choosing the output. We compare
the online-LOCAL model with three other models: the LOCAL model of distributed
computing, where each node produces its output based on its radius-T
neighborhood, its sequential counterpart SLOCAL, and the dynamic-LOCAL model,
where changes in the dynamic input graph only influence the radius-T
neighborhood of the point of change. The SLOCAL and dynamic-LOCAL models are
sandwiched between the LOCAL and online-LOCAL models, with LOCAL being the
weakest and online-LOCAL the strongest model. In general, all models are
distinct, but we study in particular locally checkable labeling problems
(LCLs), which is a family of graph problems studied in the context of
distributed graph algorithms. We prove that for LCL problems in paths, cycles,
and rooted trees, all models are roughly equivalent: the locality of any LCL
problem falls in the same broad class - $O(\log^* n)$, $\Theta(\log n)$, or
$n^{\Theta(1)}$ - in all four models. In particular, this result enables one to
generalize prior lower-bound results from the LOCAL model to all four models,
and it also allows one to simulate e.g. dynamic-LOCAL algorithms efficiently in
the LOCAL model. We also show that this equivalence does not hold in general
bipartite graphs. We provide an online-LOCAL algorithm with locality $O(\log
n)$ for the $3$-coloring problem in bipartite graphs - this is a problem with
locality $\Omega(n^{1/2})$ in the LOCAL model and $\Omega(n^{1/10})$ in the
SLOCAL model.
