  This paper introduces several new algorithms for consensus over the special
orthogonal group. By relying on a convex relaxation of the space of rotation
matrices, consensus over rotation elements is reduced to solving a convex
problem with a unique global solution. The consensus protocol is then
implemented as a distributed optimization using (i) dual decomposition, and
(ii) both semi and fully distributed variants of the alternating direction
method of multipliers technique -- all with strong convergence guarantees. The
convex relaxation is shown to be exact at all iterations of the dual
decomposition based method, and exact once consensus is reached in the case of
the alternating direction method of multipliers. Further, analytic and/or
efficient solutions are provided for each iteration of these distributed
computation schemes, allowing consensus to be reached without any online
optimization. Examples in satellite attitude alignment with up to 100 agents,
an estimation problem from computer vision, and a rotation averaging problem on
$SO(6)$ validate the approach.
