1. A method for discovery, comprising: grouping a set of nodes that can fetch same information; after a first discovery stage, selecting a portion of the set of nodes, using a processor, to perform an additional discovery stage based on a decision of each node; and performing the additional discovery stage with the portion of the set of nodes wherein each node makes a decision whether to perform the additional discovery stage, wherein selecting the portion of the set of nodes includes specifying a number of nodes from the set of nodes to perform the additional discovery stage in accordance with a fixed probability assigned for different node set sizes and discovery constraints, and specifying the number of nodes includes deciding that only every dth node in the portion performs the additional discovery stage, where d depends on the probability and local knowledge on the nodes about the other nodes from the set.