Local Computation "What can be computed locally?"[Naor,Stockmeyer'93] the LOCAC model [Linial '87]: Communications are synchronized. In each round:each node can exchange unbounded messages with all neighbors,perform unbounded local computation,and read/write to unbounded local memory. Complexity:of rounds to terminate in the worst case. In t rounds:each node can collect information up to distance t. PLOCAL:t=polylog(n)Local Computation • Communications are synchronized. • In each round: each node can exchange unbounded messages with all neighbors, perform unbounded local computation, and read/write to unbounded local memory. • Complexity: # of rounds to terminate in the worst case. • In t rounds: each node can collect information up to distance t. the LOCAL model [Linial ’87]: “What can be computed locally?” [Naor, Stockmeyer ’93] PLOCAL: t = polylog(n)