The quantity and capabilities of smart devices and sensors deployed as part of the Internet of Things (IoT) and accessible via remote microservices is set to rise dramatically as the provision of interactive data streaming increases. This introduces opportunities to rapidly construct new applications by interconnecting these microservices in different workflow configurations. The challenge is to discover the required microservices, including those from trusted partners and the wider community, whilst being able to operate robustly under diverse networking conditions. This paper outlines a workflow approach that provides decentralized discovery and orchestration of verifiably trustable services in support of multi-party operations. The approach is based on adoption of patterns from self-sovereign identity research, notably Verifiable Credentials, to share information amongst peers based on attestations of service descriptions and prior service usage in a privacy preserving and secure manner. This provides a dynamic, trust-based framework for ratifying and evaluating the qualities of different services. Collating these new service descriptions and integrating with existing decentralized workflow research based on vector symbolic architecture (VSA) provides an enhanced semantic search space for efficient and trusted service discovery that is necessary to support a diverse range of emerging edge-computing environments. An architecture for a dynamic decentralized service discovery system, is designed, and described through application to a scenario which uses trusted peers’ reported experiences of an anomaly detection service to determine service selection.