As the Cloud computing appears to be part of the mainstream computing in a few years, the number of the services it provides, its users, and the requests of these services will be on the rise accordingly. To deliver satisfactory experience to Cloud users, it is essential that highly scalable techniques for service discovery should be available. We embarked on a preliminary study, in Cloud environments, on service discovery by adopting an unstructured P2P technique. In the context of Cloud computing, we start by examining proposed and deployed solutions to service discovery, discuss the methodology of developping efficient mechanisms for service description, description indexing, and query routing, and finally identify open issues.