||Decentralized workflows require a means of specifying distributed data and computing control dependencies amongst services without the centralized coordination of the flow. The distributed nature of such workflows put far more emphasis on discovery mechanisms to ensure that each node can operate completely in an autonomous manner while cooperating with each other when needed. Consequently, the workflow must be capable of discovering nodes it needs to interact along with their associated connections in the most resource efficient way possible. To this end, a scheme for distributing the coordination information is needed that can minimize communication overhead, whilst providing comprehensive information surrounding the workflow being executed - tasks, dependencies, location, metadata, and so forth. In this paper, we explore the use of structured associative memory models called vector symbolic architectures, from the artificial intelligence community, for representing and orchestrating complex decentralized workflows. Such an approach offers a number of desirable features: (a) it can encode workflows containing multiple coordinated sub-workflows in a way that allows the workflow logic to be unbound on-the- y and executed in a completely decentralized way; (b) the workflow and associated complex metadata can be embedded into a single vector; (c) the vector representation is extremely compact; and (d) it is completely self contained and can be passed around using standard group transport protocols to support mobile ad hoc networks. We first describe the overview of the approach and apply the methodology to serial and complex workflows. We then describe the design and implementation of the system, and apply it to encode and reconstruct five of the Pegasus workflows—i.e., Montage, CyberShake, Epigenomics, Inspiral Analysis, and SIPHT—to demonstrate its viability.