An automated workflow services system can accommodate a wide variety of workflow scenarios. A composition service, a constraint service, and a tracking service can be provided to client programs. The composition service can support client-directed instantiation of actions for activity flows. Activity flows can be based on an activity model, constructed on an ad hoc basis, or a combination thereof. Actions can be added to an activity flow at execution time of the activity flow. The tracking service can track messages to and from the actions.