  We study nondeterministic and probabilistic versions of a discrete dynamical
system (due to T. Antal, P. L. Krapivsky, and S. Redner) inspired by Heider's
social balance theory. We investigate the convergence time of this dynamics on
several classes of graphs. Our contributions include:
  1. We point out the connection between the triad dynamics and a
generalization of annihilating walks to hypergraphs. In particular, this
connection allows us to completely characterize the recurrent states in graphs
where each edge belongs to at most two triangles.
  2. We also solve the case of hypergraphs that do not contain edges consisting
of one or two vertices.
  3. We show that on the so-called "triadic cycle" graph, the convergence time
is linear.
  4. We obtain a cubic upper bound on the convergence time on 2-regular triadic
simplexes G. This bound can be further improved to a quantity that depends on
the Cheeger constant of G. In particular this provides some rigorous
counterparts to previous experimental observations.
  We also point out an application to the analysis of the random walk algorithm
on certain instances of the 3-XOR-SAT problem.
