  A new parallel algorithm for simulating Ising spin systems is presented. The
sequential prototype is the n-fold way algorithm cite{BKL75}, which is
efficient but is hard to parallelize using conservative methods. Our parallel
algorithm is optimistic. Unlike other optimistic algorithms, e.g., Time Warp,
our algorithm is synchronous. It also belongs to the class of simulations known
as ``relaxation'' cite{CS8 hence it is named ``synchronous relaxation.'' We
derive performance guarantees for this algorithm. If N is the number of PEs,
then under weak assumptions we show that the number of correct events processed
per unit of time is, on average, at least of order N/log(N). All communication
delays, processing time, and busy waits are taken into account.
