Local Computation "What can be computed locally?" [Noar,Stockmeyer,STOC'93,SICOMP'95] the LOCAC model [Linial '87]: ● Communications are synchronized. In each round:each node can send messages of unbounded sizes to all its neighbors. Local computations are free. 0 Complexity:of rounds to terminate in the worst case. In t rounds:each node can collect information up to distance t.Local Computation • Communications are synchronized. • In each round: each node can send messages of unbounded sizes to all its neighbors. • Local computations are free. • 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]