  We study $k$-star decompositions, that is, partitions of the edge set into
disjoint stars with $k$ edges, in the uniformly random $d$-regular graph model
$\mathcal{G}_{n,d}$. We prove an existence result for such decompositions for
all $d,k$ such that $d/2 < k \leq d/2 + \max\{1,\frac{1}{6}\log d\}$. More
generally, we give a sufficient existence condition that can be checked
numerically for any given values of $d$ and $k$. Complementary negative results
are obtained using the independence ratio of random regular graphs. Our results
establish an existence threshold for $k$-star decompositions in
$\mathcal{G}_{n,d}$ for all $d\leq 100$ and $k > d/2$, and strongly suggest the
a.a.s. existence of such decompositions is equivalent to the a.a.s. existence
of independent sets of size $(2k-d)n/(2k)$, subject to the necessary
divisibility conditions on the number of vertices.
  For smaller values of $k$, the connection between $k$-star decompositions and
$\beta$-orientations allows us to apply results of Thomassen (2012) and
Lov\'asz, Thomassen, Wu and Zhang (2013). We prove that random $d$-regular
graphs satisfy their assumptions with high probability, thus establishing
a.a.s. existence of $k$-star decompositions (i) when $2k^2+k\leq d$, and (ii)
when $k$ is odd and $k < d/2$.
