Distributed Stochastic Graph Algorithms
Keren Censor-Hillel, Aditi Dudeja, George Giakkoupis · 2026
We study stochastic graph optimization problems in a novel distributed setting. As in the standard centralized setting, a random subgraph G* of a known base graph G is realized by including each edge e independently with a known probability pe, and we must solve an optimization problem on G* despite uncertainty about its edges. In the standard setting, to cope with this uncertainty, the algorithm can query any edge of G to learn if the edge exists in G*, and its complexity is the number of queried edges. The distributed setting incorporates uncertainty in a natural manner, by having each vertex know only about its own edges in G* (and only communicate over them), and the complexity is measured by the number of synchronous communication rounds.