The topic of this thesis is the issue of locality in distributed computing. A first set of results in this thesis concerns the $\Delta$-vertex coloring problem. They are all based on the following result. Let $G$ be a graph such that $\Delta \ge 3,G$ is not a complete graph, and such that all of $G$ except one vertex $v$ is $\Delta$-colored. Then, it is possible to extend this $\Delta$-coloring to all of $G$ by recoloring a path originating from $v$ of length at most $O(\log \Delta n)$. This property allows us to develop several efficient algorithms for $\Delta$-coloring. In particular, but not exclusively, in the distributed and PRAM models of computation. It also implies a well-known result of Brooks as a corollary. Another set of results concerns network decomposition - a basic notion in distributed graph algorithms. We improve the bounds for computing a network decomposition distributively and deterministically. Our algorithm computes an $(nϵ(n),nϵ(n))$-decomposition in $O(nϵ(n))$ time, where $ϵ(n)=O(1/\log n)$. We also show that the class of graphs $G$ whose maximum degree is $O(n\delta (n)$, where $\delta (n)=O(1/\log \log n)$, is complete for the task of computing a ($\log n,\log n)$-decomposition, in polylogarithmic in $n$ time. Completeness is to be intended in the following sense: if we have an algorithm $A$ that computes a $(\log n,\log n)$-decomposition in polylogarithmic in $n$ time for graphs in $G$, then we can compute a $(\log n,\log n)$-decomposition in polylogarithmic in $n$ time for all graphs. A last set of results concerns the edge coloring problem. We give a randomized distributed algorithm to compute an edge coloring of a given network $G$, that uses at most $1.6\Delta +\log 2+\delta n$ colors, for any $\delta greaterthan0$. The running time is $O(\log n)$ and the failure probability is at most $ϵ$, for any fixed $ϵgreaterthan0$. The algorithm is quite simple but requires an interesting probabilistic analysis. At the core of the analysis is an extension of the Chernoff-Hoeffding bounds, which are fundamental tools used in estimating the tail probabilities of the sum of Bernoulli-like trials.