  We present a new dynamic partial-order reduction method for stateless model
checking of concurrent programs. A common approach for exploring program
behaviors relies on enumerating the traces of the program, without storing the
visited states (aka stateless exploration). As the number of distinct traces
grows exponentially, dynamic partial-order reduction (DPOR) techniques have
been successfully used to partition the space of traces into equivalence
classes (Mazurkiewicz partitioning), with the goal of exploring only few
representative traces from each class.
  We introduce a new equivalence on traces under sequential consistency
semantics, which we call the observation equivalence. Two traces are
observationally equivalent if every read event observes the same write event in
both traces. While the traditional Mazurkiewicz equivalence is control-centric,
our new definition is data-centric. We show that our observation equivalence is
coarser than the Mazurkiewicz equivalence, and in many cases even exponentially
coarser. We devise a DPOR exploration of the trace space, called data-centric
DPOR, based on the observation equivalence. For acyclic architectures, our
algorithm is guaranteed to explore exactly one representative trace from each
observation class, while spending polynomial time per class. Hence, our
algorithm is optimal wrt the observation equivalence, and in several cases
explores exponentially fewer traces than any enumerative method based on the
Mazurkiewicz equivalence. For cyclic architectures, we consider an equivalence
between traces which is finer than the observation equivalence; but coarser
than the Mazurkiewicz equivalence, and in some cases is exponentially coarser.
Our data-centric DPOR algorithm remains optimal under this trace equivalence.
