[] Overview
[] Routing Protocols and Knowledge Management
[] High Level Communication Constructs
[] Simple Collaboration - Service-oriented Computing
[] Advanced Collaboration - Workflow Management
Flexible Workflows
As discussed in my work on logical mobility of services, rigidity in any form in a MANET environment is a liability. In current workflow technology, the structure and semantics of a workflow are specified a priori and do not evolve at runtime. My first step in building a collaborative system for MANETs based on workflows was to design a specification for flexible and adaptive workflows that could change in response to environmental conditions. The key problem here was to strike a balance between the structured organization of a traditional workflow and the dynamism and flexibility demanded by the MANET environment.
My contribution in this area is the concept of filters, which precede and succeed each task and are used to specify rich synchronization semantics that are guided by contextual information. The filters contain selection conditions that can be applied to one or more edges. These conditions are tests against environmental parameters obtained through sensors or via the knowledge exchange protocol I developed. These conditions determine if an edge's value is to be used or discarded. For example, we may choose to use Edge A's value if the temperature is above 50F but use Edge B's value if the temperature is below 50F. In addition to the filters, I developed Accept Sets that can specify the synchronization semantics of the edges based again on contextual information. Therefore, a set of incoming edges may have AND semantics under certain conditions and OR semantics in others. These features are shown in Figure 1.
Figure 1: Flow of Information between Filters, Accept Sets, and Tasks on a Single Host
Distributed Allocation
Since workflows are usually executed collaboratively, an important aspect of workflow management is the process of determining who is responsible for performing each task in the workflow. In traditional workflows consisting of fully connected hosts, a central controller looked up a directory of suitable hosts, chose one and invoked it directly. In MANETs, the problem is to provide this same functionality but in a distributed manner while being aware of the fact that not all hosts are present and accessible at all times.
My solution uses graph cutting, measures of utility and fitness, and a bidding approach to allocate tasks to hosts. The monolithic workflow is cut into many pieces and distributed to specialized hosts called coordinators. Coordinators solicit bids from interested hosts (putting the onus of task assignment on the hosts rather than the allocator). It assigns tasks provisionally to the host with the best bid (the bid is based on having services to perform the task, specialization, and mobility pattern). It then waits until the starting time of the task approaches. If a better bid is received in the interim, it replaces the original bid. Finally, it assigns the task to the host with the most current bid by the commitment deadline for the task, which is time at which a host must leave to reach the location of the task to perform it. The mechanism for this is shown in Figure 2.
Figure 2: Distributed Allocation Protocol for Workflow Tasks Executing Across a MANET
Distributed Execution
As with all other functions that occur across a MANET, the execution of workflows must also be handled in a distributed manner. The allocation protocol provides each host with a list of tasks they must execute and the incoming and outgoing edges associated with that task. The engine on each host is designed to wait for inputs to a task before executing it and producing results. Hence, the execution begins with the first task and continues according to the structure of the workflow until all tasks are completed, without any host needing to be aware of parts of the workflow other than those it is responsible for executing. The mechanism for this is shown in Figure 3.
Figure 3: Distributed Execution of Workflow Tasks
Related Publications
Rohan Sen, Gregory Hackmann, Mart Haitjema, Gruia-Catalin Roman, and Christopher Gill, “Coordinating Workflow Allocation & Execution in Mobile Environments,” In: Proceedings of the 9th Intl. Conf. on Coordination Models & Languages, pp. 249-267, June 2007 Rohan Sen, Gruia-Catalin Roman, and Christopher Gill, “Distributed Allocation of Workflow Tasks in MANETs,” Washington University Technical Report WU-CSE-2007-41 Rohan Sen, Gruia-Catalin Roman, Christopher Gill, and Andrew Frank, “CiAN: A Workflow Engine for MANETs,” Washington University Technical Report WU-CSE-2006-51
