A service workflow agent associated with a particular service of a provider network identifies a repository in which workflow descriptors indicative of tasks to be performed by the service are stored. In response to determining that a modification has been applied at one such repository, the agent examines a particular workflow descriptor stored in the repository. The agent initiates an attempt to implement a first task indicated in the descriptor. Subsequently, the agent updates the descriptor in accordance with an optimistic concurrency control technique to indicate a status of the first task.