  We study the problem of critical slowing-down for gauge-fixing algorithms
(Landau gauge) in $SU(2)$ lattice gauge theory on a $2$-dimensional lattice. We
consider five such algorithms, and lattice sizes ranging from $8^{2}$ to
$36^{2}$ (up to $64^2$ in the case of Fourier acceleration). We measure four
different observables and we find that for each given algorithm they all have
the same relaxation time within error bars. We obtain that: the so-called {\em
Los Alamos} method has dynamic critical exponent $z \approx 2$, the {\em
overrelaxation} method and the {\em stochastic overrelaxation} method have $z
\approx 1$, the so-called {\em Cornell} method has $z$ slightly smaller than
$1$ and the {\em Fourier acceleration} method completely eliminates critical
slowing-down. A detailed discussion and analysis of the tuning of these
algorithms is also presented.
