  We investigate sandpile models where the updating of unstable columns is done
according to a stochastic rule. We examine the effect of introducing nonlocal
relaxation mechanisms. We find that the models self-organize into critical
states that belong to three different universality classes. The models with
local relaxation rules belong to a known universality class that is
characterized by an avalanche exponent $\tau \approx 1.55$, whereas the models
with nonlocal relaxation rules belong to new universality classes characterized
by exponents $\tau \approx 1.35$ and $\tau \approx 1.63$. We discuss the values
of the exponents in terms of scaling relations and a mapping of the sandpile
models to interface models.
