Abstract
We show how sampling techniques allow processors in a network to build and update a minimum spanning tree using polylog bits of communication per processor with nearly no local memory requirements. Here we assume each processor knows its neighbors only. This is the first method to build a tree without requiring communication across every edge and the first method to process an edge deletion or insertion without requiring communication across every edge or requiring each processor to keep a copy of the tree.