We discuss eleven well-known basic models of distributed computing: four message-passing models that differ by the (non-)existence of port-numbers and a hierarchy of seven local computations models. In each of these models, we study the computational complexity of the decision problem whether the leader election and/or naming problem can be solved on a given network. It is already known that this problem is solvable in polynomial time for two models and co-
-complete for another one. Here, we settle the computational complexity for the remaining eight problems by showing co-
-completeness. The results for six models and the already known co-
-completeness result follow from a more general result on graph labelings.