An overlay network, node and method for adaptive service discovery. The method uses an adaptive service discovery in the overlay network for finding a peer that provides a desired service; generates a tree structure for current peers that provide the desired service; assign the current peers that provide the desired service to different levels of the tree structure; estimate, when a peer intends to register for the desired service with the adaptive service discovery, a number S of actual peers that provide the desired service; and calculates, based on the estimated number of actual peers providing the desired service, an optimal starting level for the peer to register for the desired service.