Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates the expressiveness of distributed decision-making systems with varying computational constraints and certificate types. It demonstrates that for decision problems without certificates, polynomial time bounded by the graph size is equivalent to polynomial time bounded by the local neighborhood size. However, with certificates, the computational power depends on the certificate type, with existential certificates leading to strictly larger language classes as the time bound increases, while universal certificates exhibit surprising incomparability results.
Bounding local computation by graph size can sometimes decide languages that are undecidable even with unbounded computation, a surprising twist in distributed decision making.
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.