Routing in a peer-to-peer network is described. In an implementation, a method includes receiving at one of a plurality of nodes in a peer-to-peer network, an indication of a change in membership in the peer-to-peer network by another node in the peer-to-peer network. A report is broadcast that describes the change. The report is for receipt by each node referenced in a routing table included in the one node.