  We consider the parameterized verification problem for distributed algorithms
where the goal is to develop techniques to prove the correctness of a given
algorithm regardless of the number of participating processes. Motivated by an
asynchronous binary consensus algorithm [J. Aspnes, Fast deterministic
consensus in a noisy environment. Journal of Algorithms, 2002], we consider
round-based distributed algorithms communicating with shared memory. A
particular challenge in these systems is that 1) the number of processes is
unbounded, and, more importantly, 2) there is a fresh set of registers at each
round. A~verification algorithm thus needs to manage both sources of infinity.
In this setting, we prove that the safety verification problem, which consists
in deciding whether all possible executions avoid a given error state, is
PSPACE-complete. For~negative instances of the safety verification problem,
we~also provide exponential lower and upper bounds on the minimal number of
processes needed for an error execution and on the minimal round on which the
error state can be covered.
