We study the problem of critical slowing-down for gauge-fixing algorit
hms (Landau gauge) in SU(2) lattice gauge theory on a 2-dimensional la
ttice. We consider five such algorithms, and lattice sizes ranging fro
m 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 alg
orithm they all have the same relaxation time within error bars. We ob
tain that the so-called Los Alamos method has a dynamic critical expon
ent z approximate to 2, the overrelaxation method acid the stochastic
overrelaxation method have z approximate to 1, the so-called Cornell m
ethod has z slightly smaller than 1 and the Fourier acceleration metho
d completely eliminates critical slowing-down. A detailed discussion a
nd analysis of the tuning of these algorithms is also presented.