Abstract-Many composite computational activities are modeled as directed acyclic graphs called workflows in which each vertex is a task and each directed edge represents both precedence and possible communication from its originating vertex to its ending vertex. When the execution of a task is completed, the communication with its successor(s) starts and anticipated data are transferred. Only after all parents of a task are completed and their results (if any) are received by the task its execution can start. These constraints restrict a more general case in which some tasks could communicate during their executions. In this paper, a task-model composed of both interaction and precedence of tasks is introduced. It is shown that this kind of graph can be transformed into an extended directed acyclic graphs, called hybrid directed acyclic graph, composed of tasks and super-tasks. Supertasks need not be recognized manually and the proposed method automatically finds them. This can simplify the design of complex workflows. Validity conditions of hybrid directed acyclic graphs are investigated and a verification algorithm is developed. Also, scheduling aspects of hybrid workflows on the cloud is highlighted and some results are reported. This inventive idea can open a whole new area of research and practice in the field of workflow modeling and scheduling.

Keywords