  Commutativity has proven to be a powerful tool in reasoning about concurrent
programs. Recent work has shown that a commutativity-based reduction of a
program may admit simpler proofs than the program itself. The framework of
lexicographical program reductions was introduced to formalize a broad class of
reductions. Approaches based on this framework, however, were limited to
program models with a fixed number of threads. In this paper, we show that it
is possible to define an effective parametric family of program reductions that
can be used to find simple proofs for parameterized programs, i.e., programs
with an unbounded number of threads. We show that reductions are indeed useful
for the simplification of proofs of parameterized programs, in a sense that can
be made precise: A reduction of a parameterized program may admit a proof which
uses fewer or less sophisticated ghost variables. The reduction may therefore
be within reach of an automated verification technique, even when the original
parameterized program is not. We introduce a notion of reductions for
parameterized programs such that the reduction $\mathcal{R}$ of a parameterized
program $\mathcal{P}$ is again a parameterized program (the thread template of
$\mathcal{R}$ is obtained by source-to-source transformation of the thread
template of $\mathcal{P}$). Consequently, existing techniques for the
verification of parameterized programs can be directly applied to $\mathcal{R}$
instead of $\mathcal{P}$. We define an appropriate family of pairwise
preference orders which can be used to produce different lexicographical
reductions. To determine whether this theoretical foundation amounts to a
usable solution in practice, we have implemented the approach, based on a
recently proposed framework for parameterized program verification. The results
of our preliminary experiments on a representative set of examples are
encouraging.
