Abstract: In papers by Alon, Pach, Pinchasi, Radoicic, Sharir and Fox, Gromov, Lafforgue, Naor, Pach it is demonstrated that families of graphs with the edge relation given by a semialgebraic relation of bounded complexity satisfy much stronger regularity properties than arbitrary graphs, and can be decomposed into very homogeneous semialgebraic pieces modulo a small mistake (for example the incidence relation between points and lines on the real plane, or higher dimensional analogues). We show that in fact the theory can be developed for families of graphs whose edge relation is uniformly definable in a structure satisfying a certain model theoretic property called distality, with respect to a large class of measures. Moreover, distality characterizes these strong regularity properties. The result is similar in spirit to the recent algebraic regularity lemma of Tao, but covers an orthogonal class of examples (and applies in particular to graphs definable in arbitrary o-minimal theories and in p-adics). Joint work with Sergei Starchenko.