Search papers, labs, and topics across Lattice.
This paper analyzes three distributed classification systems: one with unbounded computation and two with polynomial-time bounded local computation, differing in whether the polynomial bound is relative to the graph size or the node's neighborhood size. The authors demonstrate that for decision *without* certificates, the two polynomial-time definitions are equivalent, as nodes cannot know the graph size. Surprisingly, for decision with universal certificates, bounding the running time by the graph size can enable deciding languages undecidable even with unbounded certificates.
Sometimes, knowing less (limiting computation to polynomial time) can let you decide *more* in distributed systems, especially with universal certificates.
We consider three classification systems for distributed decision tasks: With unbounded computation and certificates, defined by Balliu, D'Angelo, Fraigniaud, and Olivetti [JCSS'18], and with (two flavors of) polynomially bounded local computation and certificates, defined in recent works by Aldema Tshuva and Oshman [OPODIS'23], and by Reiter [PODC'24]. The latter two differ in the way they evaluate the polynomial bounds: the former considers polynomials with respect to the size of the graph, while the latter refers to being polynomial in the size of each node's local neighborhood. We start by revisiting decision without certificates. For this scenario, we show that the latter two definitions coincide: roughly, a node cannot know the graph size, and thus can only use a running time dependent on its neighborhood. We then consider decision with certificates. With existential certificates ($\Sigma_1$-type classes), a larger running time defines strictly larger classes of languages: when it grows from being polynomial in each node's view, through polynomial in the graph's size, and to unbounded, the derived classes strictly contain each other. With universal certificates ($\Pi_1$-type classes), on the other hand, we prove a surprising incomparability result: having running time bounded by the graph size sometimes allows us to decide languages undecidable even with unbounded certificates. We complement these results with other containment and separation results, which together portray a surprisingly complex lattice of strict containment relations between the classes at the base of the three classification systems.
