  We present fast and efficient randomized distributed algorithms to find
Hamiltonian cycles in random graphs. In particular, we present a randomized
distributed algorithm for the $G(n,p)$ random graph model, with number of nodes
$n$ and $p=\frac{c\ln n}{n^{\delta}}$ (for any constant $0 < \delta \leq 1$ and
for a suitably large constant $c > 0$), that finds a Hamiltonian cycle with
high probability in $\tilde{O}(n^{\delta})$ rounds (the notation $\tilde{O}$
hides a $\text{polylog}(n)$ factor). Our algorithm works in the (synchronous)
CONGEST model (i.e., only $O(\log n)$-sized messages are communicated per edge
per round) and its computational cost per node is sublinear (in $n$) per round
and is fully-distributed (each node uses only $o(n)$ memory and all nodes'
computations are essentially balanced).
  Our algorithm improves over the previous best known result in terms of both
the running time as well as the edge sparsity of the graphs where it can
succeed; in particular, the denser the random graph, the smaller is the running
time.
