Methods and apparatus for enhanced overlay state maintenance in a peer-to-peer overlay network. A first method includes inferring that a first node is leaving the overlay network, and transmitting a decrement message to decrement a size counter value. A second method includes identifying a set of nodes associated with a first node of an overlay network, obtaining a segment length associated with each node of the set of nodes, and determining a size of the overlay network by dividing the total number of nodes in the set of nodes by the sum of the segment lengths. A third method includes identifying a set of nodes associated with a first node of an overlay network, obtaining a size estimate associated with the first node and with each node of the set of nodes, and determining a size of the overlay network by averaging the size estimates.