  We introduce a novel concept termed "stochastic distance" for property
testing. Diverging from the traditional definition of distance, where a
distance $t$ implies that there exist $t$ edges that can be added to ensure a
graph possesses a certain property (such as $k$-edge-connectivity), our new
notion implies that there is a high probability that adding $t$ random edges
will endow the graph with the desired property. While formulating testers based
on this new distance proves challenging in a sequential environment, it is much
easier in a distributed setting. Taking $k$-edge-connectivity as a case study,
we design ultra-fast testing algorithms in the CONGEST model. Our introduction
of stochastic distance offers a more natural fit for the distributed setting,
providing a promising avenue for future research in emerging models of
computation.
