Workflow modeling

Christian Stefansen

                              cstef@diku.dk

2003-06-18

Self-evident, adj. Evident to one’s self and to nobody else.

– Devil’s Dictionary

NEXT

Workflow modeling cstef@diku.dk

Agenda

• The four universal flow constructs

• Motivating example for using a calculus

• Introducing the π-Calculus

• The π-Calculus meets REA in action

• Open issues

• Bonus if time: Formal stuff to impress friends with

Workflow modeling cstef@diku.dk

The Four Universal Constructs

A brief look at these flow/process languages

• BPEL (formerly XLANG and WSFL), ebXML, UML Activity Diagrams

supports the idea of four universal constructs:

• Sequence

• Parallelization

• Iteration/recursion

• Selection (Taken from [9] where reference is given to Aalst [1].)

Workflow modeling cstef@diku.dk

An Example Workflow

0.

1.

2.  3.
4.  5.

6.

7.

8. Receive order Reject Accept Procurement Inventory requisition Received Package ready Ship Send invoice

Each state may be an abstraction over an invocation.

Workflow modeling cstef@diku.dk

π-Calculus Syntax^{1}

The π-Calculus has the following syntax

P ::= 0  (inaction)
| P_{1} + P_{2} (summation i.e. choice)
| \overline{y}x.P  (output prefix)
| y(x).P (input prefix)
| τ.P  (silent prefix)
| P_{1}|P_{2}  (parallel composition)
| (x)P  (restriction)
| !P  (replication)

where

x, y ∈ N  (names)
P, Q, R, … ∈ P (process expressions)

\begin{matrix}Restriction \\ Prefix \\ Replication \end{matrix} \} > Composition > Summation

1This particular version of the syntax was shamelessly ganked from [5] and adapted slightly.

NEXT 4

The Example Expressed in the π-Calculus

We use channels order, inventory, procurement,
shipping, invoice.

Assume x carries customer identification, line items etc. and assume that appropriate subsystems to handle inventory, procurement, shipping, and invoicing exist.

order(x) . (\overline{order} decline +

               (\overline{order} accept

. ((\overline{inventory}x | \overline{procurement} x)

| inventory(x′). procurement(x′′)

. \overline{shipping} x′. \overline{shipping} x′′

. \overline{invoice} x′. \overline{invoice} x′′)))

The calculus focuses on what is observable i.e. communication. Every transition produces data, whereas the state reflects commitments (the future).

Types of Accounting

Financial Accounting The process of producing financial statements for external constituencies—people outside the organization, such as shareholders, creditors, and governmental authorities. This process is heavily constrained by standard-setting, regulatory, and tax authorities and the auditing requirements of independent accountants (contrast with management accounting).

Management Accounting A value-adding improvement process of planning, designing, measuring, and operating nonfinancial and financial information systems that guides management action, motivates behavior, and supports and creates the cultural values necessary to achieve an organization’s strategic, tactical, and operating objectives.

Atkinson, Banker, Kaplan, and Young [2]

The economic events and scarce economic ressources of the REA model lie primarily within the sphere of financial accounting.

Here every observable event in the firm is registered so the system lends itself very well to the broader concept of management accounting.

Workflow modeling cstef@diku.dk

The Trivial Firm

Consider a company that only permits four simple events:

• Sell goods

• Receive money

• Buy goods

• Pay money Setting

σ sales π purchases
γ goods $ money

yields the process expression

F = ((\overline{σ}_{1}γ | σ_{2}($)) . F) | ((\overline{π}_{1}$|π_{2}(γ)) . F). But something is fishy—what?

Workflow modeling cstef@diku.dk

The Trivial Firm—Correct Version

Perhaps with + instead? The expression

F = ((\overline{σ}_{1}γ | σ_{2}($)) + F) | ((\overline{π}_{1}$|π_{2}(γ)) + F) blocks. Once \overline{σ}_{1}γ, say, has occured, the inference rule of the operational semantics for sum

\frac{P →^{α} P′}{P + Q →^{α} P′}

states that the remaining +F is discarded. So no other sale can be initiated. A more sound approach is

F = (\overline{σ}_{1}γ | σ_{2}($) + \overline{π}_{1}$|π_{2}(γ)) | F which allows an arbitrary number of simultaneous transactions in progress. By the definition of replication

!F =^{{new \atop ↷}}F | !F

it simplifies to F = !(\overline{σ}_{1}γ | σ_{2}($) + \overline{π}_{1}$|π_{2}(γ)).

Workflow modeling cstef@diku.dk

The Fundamental Theorem of Accounting^{2}

Assets = Liabilities+ Equity

This is our minimal demand: To derive an income statement and a balance that obey this invariant. Let’s take a few transaction examples for the firm:

1. Receives a cookie worth $1
2. Receives an icecream worth $3
3. Sells a cookie for $2
4. Sells an icecream for $4
5. Receives money for cookie $2
6. Pays for icecream $3

(Income period ends)

2Often equity is considered part of the liabilities giving the simpler expression Assets = Liabilities NEXT 9

Workflow modeling cstef@diku.dk

Operational Semantics [6]

Transaction Examples

Let γ_{c} = cookie and γ_{i} = icecream ingoing. Let γ′_{c} = cookie and γ′_{i} = icecream outgoing.

F  =  !((\overline{σ}_{1}γ | σ_{2}($)) | (\overline{π}_{1}$|π_{2}(γ)))
F →^{π1(γc)} \overline{π}_{1}$ | F
→^{π2(γi)} \overline{π}_{1}$ | \overline{π}_{2}$ | F
→^{\overline{σ}3γ′c}  \overline{π}_{1}$ | \overline{π}_{2}$ | σ_{3}($) | F
→^{\overline{σ}4γ′i}  \overline{π}_{1}$ | \overline{π}_{2}$ | σ_{3}($) | σ_{4}($) | F
→^{σ3($)} \overline{π}_{1}$ | \overline{π}_{2}$ | σ_{4}($) | F
→^{\overline{π}2$}  \overline{π}_{1}$ | σ_{4}($) | F

The trace is π_{1}(γ_{c}), π_{2}(γ_{i}), \overline{σ}_{3}γ′_{c}, \overline{σ}_{4}γ′_{i}, σ_{3}($), \overline{π}_{2}$. Each transition has produced REA data. The commitments are reflected in the state \overline{π}_{1}$ | σ_{4}($) | F.

Now the income statement and the balance sheet can be derived...

Deriving the General Ledger

Every trace member gives rise to one transaction line. For now, this piece of pseudo-code for the trace consolidation function θ will suffice:

θ( ($)) → Petty cash
θ(\overline{α} x) → Income
θ(α(x)) → Expenses

Notice that all outputs are credited and all inputs are debited.

Using a valuation function υ, every commitment contributes to the balance sheet. The states are mapped in a similar fashion to A/R and A/P respectively.

υ(\overline{α} x) → A/P
υ(α(x)) → A/R

Workflow modeling cstef@diku.dk

Income Statement and Balance Sheet

Very simple, stylized general ledger. Balance sheet:

Assets A/R (st) $4  Liabilities A/P (st) $1
Petty cash (5) $2 (6) $3  Equity

Income statement:

Expenses (1) $1 (2) $3 Income (3) $2 (4) $4

The gross profit of $2 is transferred to equity, and we have Assets ($3) = Liabilities($1) + Equity($2).

Open Issues

What calculus is best suited? The π-Calculus lacks good constructs for sequentiality, leaves “stuck states”/deadlocks, is data-unaware, and perhaps too general.

What is a channel? Ontologically speaking Soundness For what subset of process expressions do θ

and υ produce valid financial statements? Duality How can the duality constraint be enforced? Timing How should timing be introduced? Policies How does one express policies? Model checking? Valuation How should valuation be done? What is υ(P +

Q)? Exceptions What if a customer never pays? Should all such

contingencies be expressed explicitly in the process expression?

Contact

Christian Stefansen

N208, DIKU

 cstef@diku.dk
http://www.stefansen.dk

Bonus Stuff—The Expansion Law (simplified version [8])

For the mathematically inclined it may be interesting to notice that

P |Q = ∑_{P \underrightarrow{μ}P ′} μ.(P′|Q) + ∑_{Q\underrightarrow{μ}Q′} μ.(P |Q′) +

∑_{{P \underrightarrow{α}P ′ \atop Q\underrightarrow{\overline{α}}Q′}} τ.(P′|Q′).

Hence composition can be expressed using summation by the expansion law. It is sometimes easier to realize that this identity actually holds by considering the simply indentity a|b = a.b + b.a first.

Bonus Stuff—π-Calculus Variations

One may elect to restrict the syntax to guarded sums i.e. ∑_{i∈I} α_{i}.P_{i} because it reduces the practical problem of omniscient global decisions and thus simplifies the theory somewhat ([7] p. 17). Match can be expressed using the other constructs [5]. If we take π to range over prefixes a considerably simpler syntax can be obtained as:

π ::= x(y) (input)
| \overline{x}y  (output)
| τ  (silent)
P ::= ∑_{i∈I} α_{i}.P_{i} (summation i.e. choice)
| P_{1}|P_{2}  (parallel composition)
| (x)P  (restriction)
| !P  (replication)

The historic development of the π-Calculus:

Relabelling → Defined agents → Replication

References

[1] W. van der Aalst and K. van Hee: Workflow Management, MIT Press, 2002

[2] Atkinson, Banker, Kaplan, Young: Management Accounting, third international ed., Prentice Hall, 2001

[3] BPEL (Business Process Execution Language)

ftp://www6.software.ibm.com/software/
developer/library/ws-bpel11.pdf
[4] ebXML http://www.ebxml.org/specs/ebBPSS.pdf

[5] Robin Milner and Joachim Parrow and David Walker: A Calculus of Mobile Processes, Part I,

http://citeseer.nj.nec.com/article/ mil-
ner89calculus.html

[6] Robin Milner and Joachim Parrow and David Walker: A Calculus of Mobile Processes, Part II,

http://citeseer.nj.nec.com/article/ mil-
ner89calculus.html

[7] Joackim Parrow: An Introduction to the π-Calculus,

http://www.ifi.uio.no/dbsem/foils2003vaar/
introPiCalculus.pdf

[8] David Sands: Models of Concurrent Computation, handwritten lecture notes from a course given at DIKU

[9] Ole Bue Lond and Jakob Rauhe: Accommodating

Workflow modeling cstef@diku.dk

Change in Enterprise Applications, thesis, IT-University of Copenhagen