Techniques for presenting discovery window selection in a NAN environment are provided. Specifically, methods that when taken alone or together, provide a device or group of devices with an efficient way of synchronizing and communicating with other devices is presented. The present disclosure includes a method that provides a device with the capability of locally selecting a discovery window subset that meets the current device power and application constraints. The discovery window subset is created based on a uniform distribution of discovery window selection within the set. The method describes the generation of the subsets such that set inclusion exits between any two sets.