Described are techniques and systems for service discovery on a network. A media device on the network generates a signature indicative of a particular set of one or more services available for execution on the media device. The signature may be distributed on the network using beacon transmissions from the media device. A receiving media device compares the signature with previously stored service data which associates signatures with service sets. The stored service data may include a local signature indicative of a local service set. Determinations of a match result in the receiving media device using the previously stored data. Unmatched signatures may result in the receiving media device sending a request for service set data. The received service set data may then be used to provide service availability information. The received service set data and associated signature may be added to the stored service data.