We consider hierarchies related to distributed decision problems: unbounded computation time and unbounded certificates, as defined by Balliu, D’Angelo, Fraigniaud, and Olivetti [JCSS’18], and two other hierarchies that polynomially bound computation and certificate size, defined by Aldema Tshuva and Oshman [OPODIS’23], and by Reiter [PODC’24]. The two definitions for polynomially bounded local computation differ in the parameter they are polynomial in: Aldema Tshuva and Oshman consider being polynomial in the size of the graph while Reiter considers each node being polynomial in the size of its local neighborhood.
I will define the LOCAL model of distributed computation, distributed decision tasks in this model and relationships between classes of the three hierarchies.
Based on: https://arxiv.org/pdf/2603.29477
