Transcript PPT - Swinburne University of Technology

Setting Temporal Constraints in
Scientific Workflows
Xiao Liu, Jinjun Chen, Yun Yang
CS3: Centre for Complex Software Systems and Services
Swinburne University of Technology, Melbourne, Australia
{xliu, jchen, yyang}@swin.edu.au
Content

Introduction
 Temporal Verification
 Temporal QOS Framework

Setting Temporal Constraints in Scientific Workflows
 Problem Statement
 A probabilistic strategy
 Evaluation

Conclusion
2
Introduction: Temporal Verification

Scientific workflow verification: Structure, Performance,
Resource, Authorisation, Cost and Time.

In reality, complex scientific and business processes are normally
time constrained. Hence:
 Time constraints are often set when they are modelled as
scientific workflow specifications.
 Temporal consistency states, i.e. the tendency of temporal
violations from consistency to inconsistency, need to be
verified and treated proactively and accordingly.

Temporal verification is to check the temporal consistency states
so as to identify and handle temporal violations.
3
Temporal QOS Framework

Constraint Setting
 Setting temporal constraints according to temporal QOS
specifications.

Checkpoint Selection
 Selecting necessary and sufficient checkpoints to conduct
temporal verification.

Temporal Verification
 Verifying the consistency states at selected checkpoints.

Temporal Adjustment
 Handling different temporal violations.
4
Content

Introduction
 Temporal Verification
 Temporal QOS Framework

Setting Temporal Constraints in Scientific Workflows
 Problem Statement
 A probabilistic strategy
 Evaluation

Conclusion
5
Problem Statement

Most current work adopts only few overall user specified
temporal constraints without considering system
performance.
 Few overall constraints: not applicable for local verification
and control.
 User specified constraint: frequent temporal violations, huge
exception handling costs.
6
Two Basic Requirements

Temporal constraints should facilitate both overall
coarse-grained control and local fine-grained control.
 Coarse-grained constraints refer to those assigned to the
entire workflow or workflow segments.
 Fine-grained constraints refer to those assigned to
individual activities.

Temporal constraints should be well balanced between
user requirements and system performance.
7
Probabilistic Strategy--Assumptions

Two assumptions on activity durations
 Assumption 1: The distribution of activity durations can be
obtained from workflow system logs. Without losing
generality, we assume all the activity durations follow the
normal distribution model, which can be denoted as N(µ,σ2) .
 Assumption 2: The activity durations are independent to
each other.
 Exception handling of assumptions : Using normal
transformation and correlation analysis, or moreover,
ignoring them first and then adding up afterwards.
8
Probabilistic Strategy--Definitions

Weighted Joint Normal Distribution

Specification of Activity Durations

Probability based Temporal Consistency
9
Weighted Joint Normal Distribution

The motivation for weighted joint normal distribution is to
estimate the overall completion time of the entire workflow by
aggregating the durations of all individual activities.

However, they are not in a simple linear relationship.

Our strategy is to model each activity duration as random
variables and aggregate them according to four basic controlflow structures, i.e. sequence, iteration, parallelism and
choice. Since most workflow process models can be easily
built by the compositions of the four building blocks, similarly,
we can obtain the weighted joint distribution of most workflow
processes.
10
Specification of Activity Durations

Maximum Duration, Mean Duration, Minimum Duration

The 3σ rule depicts that for any sample comes from
normal distribution model, it has a probability of
99.73% to fall into the range [µ-3 σ, µ+3 σ].

In our strategy, we have the following specification of
activity durations:
 Maximum Duration D(ai)= µ+3 σ
 Mean Duration M(ai)= µ
 Minimum Duration d(ai)= µ-3 σ
11
Probability based Temporal Consistency
12
Probabilistic Strategy—Overview
13
Example: Setting Coarse-grained Constraints
I Want the
process be
completed in
48 hours
Let me check
the probability
The negotiation process
14
Example: Setting Coarse-grained Constraints
That’s not
good, how
about 52
hours
Sir, its 70%,
do you
agree?
Adjust the constraint
15
Example: Setting Coarse-grained Constraints
Err… how long
will it take if I
want to have
90%
Then, it
increases to
85%
Adjust the probability
16
Example: Setting Coarse-grained Constraints
Ok, that’s the
deal! Let’s do
it!
It will take
us 54 hours
Negotiation result
17
Example: Setting Coarse-grained Constraints
Ok! But, sir, I need to remind you that
this is only a guarantee from statistic
sense. If we cannot make it, please
blame the guy who comes up with the
strategy!
Sorry, statistically,
no predictions can
be 100% sure!
18
Example: Setting Fine-grained Constrains

Setting fine-grained constraints for individual activities
 Assume the probability gained from the last step is θ% that is
with a normal percentile of λ. Then the fine-grained
constraints for individual activities are (µi +λσi).
 For example, if the coarse-grained temporal constraints are
of 90% consistency, that is a normal percentile of 1.28, then
the fine-grained constraint for activity ai with a distribution of
N(µi, σi2) is (µi +1.28σi).
19
Evaluation—System Environment
Overview of SwinDeW-G environment
20
Step1: Weighted Joint Distribution
21
Step2: Coarse-grained Constraint

Negotiation for coarse-grained constraint
WS~N(6210,2182)
6300s
66%
6360s
75%
6390s
79%
6400s
81%
U(WS)=6400s, λ=0.87
22
Step3: Fine-grained Constraint
23
Content

Introduction
 Temporal Verification
 Temporal QOS Framework

Setting Temporal Constraints in Scientific Workflows
 Problem Statement
 A probabilistic strategy
 Evaluation

Conclusion
24
Conclusion

Temporal verification is important in scientific workflows

Setting temporal constraints is a prior task for temporal
verification. Two basic requirements:
 User requirements & System performance
 Coarse-grained & Fine-grained temporal constraints

A probabilistic setting strategy
 Aggregation: Setting coarse-grained constraints
 Propagation: Setting fine-grained constraints

Evaluation proves to be effective
25
The End
 Thanks for
your patience and attention!
26