Local Computation "What can be computed locally?" [Noar,Stockmeyer,STOC'93,SICOMP'95] the LOCAC model [Linial '87]: ● Communications are synchronized. In each round:unlimited local computation and communication with neighbors. Complexity:of rounds to 0 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: unlimited local computation and communication with neighbors. • 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?” [Noar, Stockmeyer, STOC’93, SICOMP’95] PLOCAL: t = polylog(n)