Service-oriented computing is emerging as a paradigm for developing distributed applications. A critical issue of utilising service-oriented computing is to have a scalable, reliable and robust service discovery mechanism. However, traditional service discovery methods using centralised registries can easily suffer from problems such as performance bottleneck and vulnerability to failures in the large scalable service network, thus functioning abnormally. To address these problems, this paper proposes a peer-to-peer based decentralised service discovery approach named Chord4S. Chord4S utilises the data distribution and lookup capabilities of the popular Chord to distribute and discover services in a decentralised manner. Data availability is further improved by distributing service descriptions of functionally-equivalent services to different successor nodes that are organised into a virtual segment in the Chord circle. In addition, the Chord routing protocol is extended to support efficient discovery of multiple services with single request. This enables late negotiation of service level agreements between a service consumer and multiple service providers. The experimental evaluation shows that Chord4S achieves higher data availability and provides efficient query with reasonable overhead.