A nice example for an event-based notification system: Das E-Mail Notification System

http://www.esw-heim.tu-clausthal.de/netzwart/ens/welcome.phtml?dokid=62

A cron-job on a server is used to check the size of the mailbox-file. In case it increased, a notification is sent to a client that new mail has arrived. The notification is transformed into the blinking of a LED. Thus the check for new mail does not require the client to have its computer/the mail program to be running.

baldoni, virgillito - distributed event routing in publish, subscribe communication systems

The paper explains the pub/sub paradigm and provides a survey of solutions and algorithms that are aimed at implementing the paradigm while its main characteristic - scalability - is preserved.

@INPROCEEDINGS{virgillito03event,
  author = {Antonino Virgillito and Roberto Beraldi and Roberto Baldoni},
  title = {{On Event Routing in Content-based Publish/Subscribe through Dynamic    Networks}},
  booktitle = {Proc. of The 9th IEEE Workshop on Future Trends of Distributed Computing    Systems (FTDCS)},
  year = {2003},
  pages = {322--329},
  month = {May},
  owner = {ich},
  timestamp = {2006.08.03},
  url = {citeseer.ist.psu.edu/beraldi03event.html}
}

zeidler - a distributed publish,subscribe notifiaction service for pervasive environments (phd)

In the thesis, the author proposes a middleware to desynchronize participants of ubiquitous computing environments in space and time and that uses the publish/subscribe communication paradigm.

Three waves of computation: mainframes (one computer, many users), PCs (one computer, one user), ubiquitous (many computer, one user)/(many computer, many user). In the last wave, the user's attention becomes a scarce ressource, computers have to operate and maintain themselves.

Pervasive computing puts the focus on access to computing ressources and data everywhere in every situation. It is assumed that the user favours a personal, trusted device over non-personal, but everywhere accessible devices. The challenges for pervasive computing are explained, aiming on physical integration and spontaneous interoperation, ubiquitous data management, and location-dependente/context-aware applications. A system model and an infrastructure are sketched, requirements formulated.

An introduction to publish/subscribe systems is given.
publish/subscribe system: producers=publishers, consumers=subscribers, event notification services as mediator between producer and subscriber, subscriptions= standing request and indicatio of interest in certain notifications, events and notifications to communicate between publishers and subscribers. The notification service guarantees the delivery of events to interested parties according to subscriptions.

event = an obervable happening of interest, an observable change in the environment
To communicate an event/the observation of an event it has to reified. The reification of an event leads to a notification that consists of the data the describes the event, and is created by the observer. The same event may lead to multiple notifications varying in observer and amount of information. Notifications are forwarded by messages, or the other way around: a messages is a container for data that represents a notification.

event-based system: clients act as producers and consumers of notifications, producers may emit notifications upon observing an event. Producers are self-contained and may decided whether an event is worth notifying. If it is deemed for notification, the producer will eventually emit a notification for this event but several events may be reifid in a single notification.

subscribers react to received notifications accordingly. The interaction between subscribers and publishers is data-driven.

publish/subscribe system: notifications are sent to the event notification service and not the the consumers, notifications are forwarded to subscribers based on subscriptions registered at the notification service.

because of decoupling subscribers and producers through the event notification service, they don't know each other. The subscribers have to describe the data they want to receive by means of a subscription. [see: eugster - the many faces of publish, subscribe]. Subscribers can be producers of other notifications.

subscription-filters: channels, subject-based, type-based, content-based, concept-based (matching based on meta-data in heterogeneous environments)

To subscribers and publishers, the notification service is opaque. It may employ a centralized or a distributed implementation.

[bibtex]
@PhdThesis{zeidler2004PubSubPervasive,
  author =       "Andreas Zeidler",
  note =         "http://elib.tu-darmstadt.de/diss/000519",
  school =       "Darmstadt University of Technology",
  title =        "A Distributed Publish/Subscribe Notification Service
                 for Pervasive Environments",
  topic =        "PhD Theses",
  URL =          "http://elib.tu-darmstadt.de/diss/000519",
  year =         "2004",
  modified =     "0",
}

eugster - the many faces of publish, subscribe

The article provides an overview about the publish/subscribe communication paradigm and compares it to existing communication paradigms.

Individual point-to-point and synchronous communications lead to rigid and static applications, and make the development of dynamic large-scale applications cumbersome. To reduce the burden of application designers, the glue between the different entities in such large-scale settings should rather be provided by a dedicated middleware infrastructure, based on an adequate communication scheme.

publish/subscribe: Subscribers have the ability to express their interest in an event, or a pattern of events, and are subsequently notified of any event, generated by a publisher, which matches their registered interest.

The paper illustrates the decoupling dimensions of time, space, and synchronization through the pub/sub-paradigm. Different variants of pub/sub schemes are explained (topic-based, content-based, and type-based) as well as possible variations the trade-offs in the design and implementation of such systems.

Actual decoupling takes place by the use of a event service that accepts notify-requests from the publisher and executes the notification to the subscribers. The event service handles the registration of subscriptions. Publishers can notify about their future events through a advertise-operation. Events are asynchronously produced and consumed to the main control flow of the application.

The considered alternative communication paradigms are Message Passing, RPC, Notifications, Shared Space (tuple space), and Message Queuing (message-oriented middleware)

topic-based: events are associated to a topic and subscriptions and notifications are based on topics. Thus the communication channels get subdivided and peers are bundled. Topics (and thereby subscriptions and notifications) can hierarchically be organized. Topics are static structures.

content-based: events can be classified by their contents through selectable fields. Subscriptions and notifications classify and fulfil requirements on these fields. The classification mechanisms are Queries (SQL, XPath, ...), template matching and executable code, provided by the subscriber, that verifies whether an event is to be notified.

type-based: similar to topic-based, events are classified by their structure, read: type = event kind.

The article closes with a overview of implementation issues and highlights the fact that at implemenation level, scalability of the system becomes an issue again.

bibtex:

@article{eugster2003pubsub,
 author = {Patrick Th. Eugster and Pascal A. Felber and Rachid Guerraoui and Anne-Marie Kermarrec},
 title = {The many faces of publish/subscribe},
 journal = {ACM Comput. Surv.},
 volume = {35},
 number = {2},
 year = {2003},
 issn = {0360-0300},
 pages = {114--131},
 doi = {http://doi.acm.org/10.1145/857076.857078},
 publisher = {ACM Press},
 address = {New York, NY, USA},
 }
 

jaeger - self-organizing publish, subscribe

The paper presents an abstract of a approach for self-stabilizing pub/sub systems that are self-organizing by the use of local information and reconfiguration only. The paper references various papers on the topic of self-stabilization, self-organization and publish/subscribe mechanisms.

Self-stabilization (by Dijkstra): from any given state, the system can reach within a bounded a number of steps a given legitimate state. Once there, a self-stabilizing systems remains in this state unless failures occur. Thus failures are temporary only. Then no assumptions regarding failures are necessary, but then almost no assumptions about the system outside a legitimate state can be made.

Self-stabilization is usually realized in different layers of a system architecture, e.g. in the routing layer and in the "overlay network". The lower layer is meant to work independent of the higher layer: i.e. changes at this level are made transparent to the higher layer. Changes at a higher layer may require reorganization of lower layers. It is imparative that there are no cyclic dependencies between different layers of self-stabilizing mechanisms.

The paper then provides a survey on self-stabilizing systems that use the pub/sub paradigm and elaborates on the issue of self-organization in this context. Emphasis is put on the performance of a self-organizing system.


Bibtex:

@inproceedings{jaeger2005self_organizing,
 author = {Michael A. Jaeger},
 title = {Self-organizing publish/subscribe},
 booktitle = {DSM '05: Proceedings of the 2nd international doctoral symposium on Middleware},
 year = {2005},
 isbn = {1-59593-267-4},
 pages = {1--5},
 location = {Grenoble, France},
 doi = {http://doi.acm.org/10.1145/1101140.1101144},
 publisher = {ACM Press},
 address = {New York, NY, USA},
 }

Akyildiz, Su, Sankarasubramaniam, Cayirci - Wireless sensor networks: a survey

The paper presents potential wireless sensor network (WSN) applications, factors that influence the WSN design and a survey on existing protocols and solutions. However, the paper seems to be weak in the presentation of examples and explanation of design factors. The paper suggests that for an appropriate design of algorithms for the different layers of a communication architecture in a WSN, different aspects of communication and functionality in the WSN need to be integrated. The paper gives an overview on existing projects for wireless sensor networks.

Traditional sensing - two ways to deploy and operate a sensor:
a) single sensor deployed far from the phenomenon (*perception*), requires large sensors and complex techniques to improve the signal to noise ratio
b) several sensors (sensing only, no signal processing) transmit to central nodes where data is fused and processed, positions of sensors and topology has to be chosen carefully

sensor networks: large set of small sensor nodes, deployed inside/close to the phenomenon; positioning of nodes may be random, requires self-organization capabilities; is possible due to recent developments in micro-electro-mechanical systems (MEMS); data is (pre-)processed in the network and not at a designated central node

application scenarios: detection of chemical substances in gases and liquids

sensor networks use ad-hoc techniques; differences to (traditional) ad-hoc networks:
- (by magnitude) larger number of nodes
- densely deployed
- prone to failures
- topology changes frequently
- use of broadcast communication (ad-hoc: point-to-point)
- limited ressources and capabilities
- have no global ID, rather identified by their functionality

dense deployment -> short distance -> little power consumption for communication (despite multi-hop) and low signal power levels (necessary for military use)

most important constraint: low power consumption, idea: allow run-time tradeoffs between QoS and lifetime

Sensors for most physical and chemical phenomenons are available, allowing a large variety of applications.
- Military use: monitoring, surveillance, reconnaissance, targeting, damage assessment, ABC attack detection
- environmental: tracking of animals, monitoring of environmental conditions (relation to geographic data), forest fire detection (sensors to be deployed for long time scales), biocomplexity mapping of the environment (data integration on large temporal and spatial scales, may allow to monitor small size biodiversities -> gound-level deployment), flood detection (monitor rainfall, water level, weather), agriculture (monitor water, air, soil conditions to prevent pollution)
- health applications: (tele-)monitoring of patients, drug administration, monitoring of internal processes
- home applications: automation, smart environment
- environmental controls in office/public space (reduce energy consumption)
- disaster monitoring/relief
- robot control

facors influencing sensor/WSN design:
- fault tolerance: failure of a node (due to lack of power, physical damage, environmental influences), nodes need to be designed to sustain functionaliy upon failre of a node, different scenarios require different levels of fault tolerance
- scalability: the network must be extendable without (physically) modifying existing nodes, radion transmission range determines the required sensor density and node number for a given application
- costs
- operating environment: have to operate under tough environmental conditions in remote areas
- network topology: must be self-organizing
- hardware constraints: a node consists of (1) a sensing unit (sensor, A/D converter), (2) a processing unit (possibly plus a small storage), (3) a transceiver unit, (4) a power unit and possibly application-dependend extensions; the routing in the network and the sensing require location information at high accuracy -> location sensing unit necessary; everythig small in size, some technical details on power consumption and existing systems are given
- transmission media: different frequency bands in air and water are available, for different application scenarios, communication through laser
- power consumption: power needed for sensing, communication, data processing; use power-aware protocols and algorithms, various techniques need to applied at design time to estimate the expected power consumption

communication architecture for WSNs:
the WSN needs a sink/gateway to send data from the net to some system outside and vice versa
the protocol stack on the WSN nodes needs to integrates power and routing awareness, and data with networking protocols and promootes cooperative efforts of sensor nodes. A standard layer architecture is proposed: application layer, transport layer (maintain flow of data), network layer (routing supplied data), data link layer (power aware, minimize collisions), physical layer (simple but robust modulation and receiving techniques) with orthogonal power management plane, mobility management plane, and task management plane. The planes implement policies how certain behaviour in each layer is executed/implemented for different aspects of a WSN to achieve minimal power consumption. Several scenarios for each plane are provided.

Various example protocols for each layer a presented:
- application (protocols for sensing SMP, task scheduling and data advertisement TADAP, sensor query SQDDP), key feature is the absence of an infrastructure with individually adressable nodes
- transport (TCP and its modifications are reasonable, improves interoperability with other networks/the internet)
- network (focus on power-efficient routing) using a data-centric approach, data may be aggregated on its way through the network, routing algorithms should be adjusted accordingly. Various routing approaches and the properties are presented and discussed (the small minimum energy communication network (SMECN). flooding, gossiping, negotiation (SPIN) a variation of a pub/sub scheme with subscriptions of a short life-time, sequential assignment routing (SAR), low energy adaptive clustering hierarchy (LEACH), directed diffusion (a P2P-alike pub/sub scheme, where subscriptions originate from the sink/gateway and sensors are publishers)
- data link (it is explained why existing medium access control (MAC) cannot be applied in WSN)

Bibtex:

@article{akyildiz2002wsn_survey,
 author = {I. F. Akyildiz and W. Su and Y. Sankarasubramaniam and E. Cayirci},
 title = {Wireless sensor networks: a survey},
 journal = {Comput. Networks},
 volume = {38},
 number = {4},
 year = {2002},
 issn = {1389-1286},
 pages = {393--422},
 doi = {http://dx.doi.org/10.1016/S1389-1286(01)00302-4},
 publisher = {Elsevier North-Holland, Inc.},
 address = {New York, NY, USA},
 }

STEPHANOS ANDROUTSELLIS-THEOTOKIS AND DIOMIDIS SPINELLIS - A Survey of Peer-to-Peer Content Distribution Technologies


The paper examines a number of definitions for peer-to-peer systems and presents typical applications for P2P systems. The authors postulate a method to describe and analyze peer-to-peer-based architectures. The analysis incorporate the evaluation of design decisions for p2p systems, each of the decisions being explained and examined in detail. A well-done survey of existing architectures and implementations is given.


peer-to-peer systems: various definitions
- "pure": a network of equivalent nodes (in terms of functionality and performed tasks)
- systems with supernodes that have advanced functionality, may be chosen dynamically
- systems where noncore tasks are centralized (e.g. to increase trust in some contents etc.)

- "a class of applications that take advantages of ressources - storage, cyclye, content, human presence - available at the edges of the internet." [Shirky 2000] allows centralized servers for operations, includes grid computing

Peer-to-peer systems are distributed systems consisting of interconnected nodes able to selforganize into network topologies with the purpose of sharing resources such as content, CPU cycles, storage and bandwidth, capable of adapting to failures and accommodating transient populations of nodes while maintaining acceptable connectivity
and performance, without requiring the intermediation or support of a global centralized server or authority.

Peer-to-Peer addresses failure, Grid computing addresses infrastructure. [Foster and Iamnitchi 2003].

application categories for peer-to-peer systems.
- communication and collaboration: directly between peer computers (e.g. instant messaging)
- distributed computation: break down computationally expensive tasks in smaller work units and distribute, central coordinatio is necessary
- internet service support: additional services for distributed/internet based applications
- database systems
- content distribution: distributed storage medium (publish, search, retrieve files), can be categorized by their main purpose as application and infrastructure (i.e. proving peer-to-peer-based services for distributed applications, e.g. routing & location, anonymity, reputation management)

The proposed analysis method for p2p architectures identifies non-functional features, their relation to design features, and evaluates the design. Non-functional features: security (authenticity, privacy, availability), scalability, performance, fairness, ressource management capabilities, semantic groupig of information. A graphic illustrates their relation to orthognal design decisions that have to be made in the creation of a p2p architecture. Each of these design decisions is explained and examined in detail.

distributed object location and routing

A p2p network is formed on top of a physical network. The logical network (having its own topology, structure, etc.) is called overlay network. Its properties influence almost all features of the system. Classifications by centralization (purely decentralized architectures, nodes are servents; partially centralized networks, allowing local, dynamically assigned supernodes; hybrid decentralized, having static supernodes = servers) and network structure (done ad-hoc or based on specific rules; contents placed unstructured or structured (to improve scalability), topology is adjusted according to the contents, infeasible for rapidly changing systems, structured systems are decentralized). A survey on existing architectures, highlighting the way the overlay network is organized, is given. The Gia System is highlighted as a decentralized p2p architecture with very good scalability properties. Tapestry is a p2p architecture with self-organizing capabilities.

Depending on the chosen overlay network topology, a failure in the underlying IP network topology may cause just single or multiple failures in the overlay network. Structured p2p systems are designed to support exact resource lookups (exact identifiers are necessary), though approaches that suppot queries with partial information exist. However, structured systems being deterministic are vulnerable to attacks that exploit the structure.

content caching, replication, and management

passive replication, cache-based replication, (pro)active replication, introspective replica management techniques (observing traffic and creating replicas accordingly to meet the demand), dynamic replica management (maintain "optimal" replica distribution influenced by server capabilities, localization of requests, required number of replicas). Replication management becomes difficult at maintaining consistency, in cominbation with encryption, and in structured systems.

secure storage, routing, cryptography, access control

by using cryptographic algorithms and certifying schemes for data, by identifying and excluding malicous nodes, by authentication techniques for distributed systems (that take into account that a single physical node may have different identities in the overlay network)

provisions for anonymity and censorship resistance

by mechanisms that shield/mask/hide the true origin of a resource/file, usually an anonymizing layer has to be placed between application and network to ensure anonymity

provisions for deniability

mechanisms that ensure that a node does not know what content is stored at it and what content is forwarded by it, thus a node can deny responsability for the contents for which it provides infrastructure only

accountability and reputation, resource trading

trust-based incentives (given externally) and trade-based incentives (provided by the nodes upon participation), even micro-payment with real money for providing reliable services

content and storage management

minimal capabilities: insert, search, retrieve content
advanced: modify, remove content; is difficult wrt consistency
content expiration, content versioning, (distributed) directory structure in p2p systems to organize content, storage, bandwith, computation capacity management

semantic grouping

group contents and peers according to semantics (semantic overlay clustering) to improve information retrieval

bibtex:
@article{androutsellis2004survey_p2p,
 author = {Stephanos Androutsellis-Theotokis and Diomidis Spinellis},
 title = {A survey of peer-to-peer content distribution technologies},
 journal = {ACM Comput. Surv.},
 volume = {36},
 number = {4},
 year = {2004},
 issn = {0360-0300},
 pages = {335--371},
 doi = {http://doi.acm.org/10.1145/1041680.1041681},
 publisher = {ACM Press},
 address = {New York, NY, USA},
 }
 

Andreas Meissner, Thomas Luckenbach, Thomas Risse, Thomas Kirste, Holger Kirchner : Design Challenges for an Integrated Disaster Management Communication and Information System

The paper provides an analysis of disaster management situations and postulates requirements for IT systems that support public emergency services in the case of a disaster. The covered topics are wireless communication and integration of the respective techonolgies, application and information flow, and organizational aspects.

The user requirements in disaster response and recovery scenario that haven't been addressed properly yet are
- Integration and linkage of information
- Availability of communication, redundancy of links
- Fast data access
- Timeliness and updating of information
- Standardization of information

for traditional disaster scenarios and additionally cyber security, authentification, image processing, sensors, logistics, knowledge management, and training for the case of terrorist attacks (and urban warfare) scenrios.

The proposed and partly assumed to be existing system architecture connects various wireless networks of different size and scopes: from government authorities and public emergency forces HQs (WAN), mobile command posts (WLAN), to the individual personnel on the site (personal area network, body area network). The system shall support information push and pull.

The information flow must allow vertical (between different organizational levels) and horizontal (peers in one level) flow using voice communication and sensor information (combined with location information). Each organizational level is source and sink of information, providing information aggregation (upstream and downstream), scheduling of tasks and assignment of ressources. HQs and other stationary participants are likely to have access to large databases and computing facilities.

Bandwidth is the scarce resource in the existing communication technology, especially at "hot spots" ("most critical areas" and "most communicative areas") where many participants are connected to the same network, while there the availability of information is most crucial and has to be provided automatically without manual interaction with the user. A problem poses the integration of the different technologies into a seamless infrastructure.

Devices and network topology needs to be auto-configuring/adaptive. They should restrict themselves to their communication spheres to avoid unnecessary traffic and bandwith usage and streamline the information flow. Services and information should be discovered (and integrated) automatically which requires self-configuration capabilites on a higher level as well.

Data and Information in the system needs to be delivered fast and without errors. At the same time, the required bandwidth is limited and information distribution has to be planned in advance to avoid peaks in critical situation and provide a reserve. The system has to be scalable. The authors suggest XML as the standard data exchange format to ease information integration.

The disaster management task forces and their resources need to be allocated and scheduled according to the current sitatuation giving rise to a number of challenges:
- The current situation on location is perceived directly only by the task forces themselves.
- Task forces must be allowed to adapt the priorities of their assigned tasks to the current situation in order to allow for a fast reaction on unpredictable changes.
- Several independent organizations provide task forces, whose abilities to act effectively are mutually dependent, and whose availability is changing.

The scheduling shall avoid:

- Idling of resources because of lacking assignments
- Inadequate prioritization of a task force’s activity because of lacking situation data at the task force or at the coordination center (due to missing local or global data, respectively)
- Idling of resources because of a long-winded coordination process on-site (who will do what, when?)
- Duplicate work (due to lack of coordination)

The entire system must:

- ensure a task force member’s ability to act autonomously by providing local scheduling capability
- provide personalized schedules for task force members that are adapted to their individual situations, based on the coordination center’s global strategy
- support monitoring and logging of the activities of a task force member, dynamic adaptation of his personal schedule, and propagation to the operation center for integration into the global strategy
- allow for perception and recording of situation facts and action requirements by the on-site task forces, and for propagation to the operation center

The authors therefore propose an architecture that supports global and local task scheduling, has repositories for facts, tasks and scehdules and suitably concrete, but generally applicable models for describing disaster situations, tasks and situation facts in order to allow (semi-)automatic schedule planning. The system has to be equipped with a proper human-machine-interface. The scheduler shall not only coordinate the resources in the field but also predict allocation and moving of resources to reduce bandwidth and provide alternative solution just when they are needed in a changed situation.

bibtex:
@CONFERENCE{meissner2002designchallenges,
  author = {Meissner, Andreas and Luckenbach, Thomas and Risse, Thomas and Kirste, Thomas and Kirchner, Holger},
  title = {{Design Challenges for an Integrated Disaster Management Communication and Information System}},
  booktitle = {The First IEEE Workshop on Disaster Recovery Networks (DIREN 2002)},
  year = {2002},
  address = {New York City},
  month = {June 24},
  organization = {IEEE},
  note = {co-located with IEEE INFOCOM 2002},
  url = {http://comet.columbia.edu/~aurel/workshops/diren02/IEEE_DIREN2002_Meissner_DesignChallenges.pdf}
}

JTP : An Object-Oriented Modular Reasoning System 

Otter: An Automated Deduction System 

Aalst, Jablonski - Dealing with workflow change: identification of issues and solutions

The paper deals with the problem of changes to a given workflow during its execution (to a WF instance as well as to the WF pattern) due to ongoing change in the requirements. The authors point out that these changes are often due to the very abstract view of a WF. In the paper, a definition of a workflow type (in terms of five perspectives) is given. Based on a classification scheme for changes, several correctness issues that may arise due to change are discussed. The authors then propose to apply an inheritance based mechanism to modify workflow definitions, especially for the dynamics of a workflow. Open problems and future work are sketched.

Bibtex:

@article{vanderAalst:2000:dealing,
    annote = {introducing five perspectives on workflow, and how changes in workflow can be achieved / managed},
    author = {van der Aalst, W. M. P.  and Jablonski, S. },
    citeulike-article-id = {403744},
    journal = {International Journal of Computer Systems Science and Engineering},
    keywords = {bibtex-import},
    month = {September},
    number = {5},
    pages = {267--276},
    priority = {2},
    title = {Dealing with workflow change: identification of issues and solutions},
    volume = {15},
    year = {2000},
    ISSN = "0267-6192",
    url = {http://is.tm.tue.nl/staff/wvdaalst/publications/p112.pdf},
}

Heinl, Horn, Jablonski, Neeb, Stein, Teschke - A Comprehensive Approach to Flexibility in Workflow Management Systems

The paper illustrates and examines the necessity of flexibility in workflow management systems and suggests some general solutions to it. The classification of flexibility is less profound than "Aalst/Jablonki - Dealing with Workflow Change", but goes along the same lines.

Basic statements:
"It is almost impossible to identify all control and correction steps a priori."
"Even if a control and correction step is identified, it is not obvious whether it should be included into the workflow type(s) of the retails production process [...] Therefore, the domain experts prefer to merely model 'most relevant' control and correction paths, i.e. paths that are used frequently."

On flexibility:
"A user should have the freedom to choose between different execution paths if necessary."
"It must be possible to change the workflow management application during runtime."

Classification scheme:
Flexibility by Selection - many alternative execution paths, succinctly represented in the model
Flexibility by Adapation - modify the workflow type -> adaption

Concerning Adaption:

Co-Evolution of Modelling Language, Model, Implementation, and Instance comes into play.

Bibtex:

@inproceedings{295675,
 author = {Petra Heinl and Stefan Horn and Stefan Jablonski and Jens Neeb and Katrin Stein and Michael Teschke},
 title = {A comprehensive approach to flexibility in workflow management systems},
 booktitle = {WACC '99: Proceedings of the international joint conference on Work activities coordination and collaboration},
 year = {1999},
 isbn = {1-58113-070-8},
 pages = {79--88},
 location = {San Francisco, California, United States},
 doi = {http://doi.acm.org/10.1145/295665.295675},
 publisher = {ACM Press},
 address = {New York, NY, USA},
 }
 

v.d.Aalst, Pesic - DecSerFlow: Towards a Truly Declarative Service Flow Language.

The paper describes an declarative modeling language for workflows and hints to a corresponding verification method. The authors consider a workflow to be a set of 'tasks' that have to be executed in a specific order. In contrast to procedural modeling languages that introduce control-flow constructs to impose the intended order, they suggest to define constraints between tasks in temporal logic (LTL) that reflect the workflow modeller's intention of ordering the tasks. An execution engine translates the tasks and the LTL constraints into a Büchi automaton that accepts exactly the valid sequences of task executions. A graphical language shall be used to denote constraitns between tasks in an intuitive way.

The authors recommend to use constraint templates derived from model checking and finite-state verification that describe the contraint properties arising in practice. They suggest three types of formulas: existence formulas restricting the number of occurences of a task. Relation formulas (binary) to positively describe the temporal ordering of two tasks as well as negation formulas that describe orderings of tasks that must not occur during the execution of a workflow. An execution is successful if in the end, all constraints of the workflow are satisfied. The authors suggest some extension of binary to n-ary relation and negation formulas.

The paper exercises the approach by the Acme Travel example and closes with a discussion of how derive an operational model from the constraints that enables the enacment of a declaratively specified workflow. The authors suggest to translate each constraint into a (non-deterministic) Büchi automaton accepting all traces that satisfy the contraint, and then to parallely compose the automata of all constraints or to build a single automaton from the conjunction of all constraints. The automaton, dealing with non-determinism, then has to work on sets of (possible) states instead of single states. The acceptance critertion needs to be modified to deal with finite traces. Either extend traces with by repeating an "end" action infinitely often, or use Büchi automata for finite traces and introduce an "init" action to accept empty traces as well. [11]

@inproceedings{AalstP:2006:decSerFlow,
  author    = {Wil M. P. van der Aalst and
               Maja Pesic},
  title     = {{DecSerFlow: Towards a Truly Declarative Service Flow Language.}},
  booktitle = {WS-FM},
  year      = {2006},
  pages     = {1-23},
  doi       = {http://dx.doi.org/10.1007/11841197_1},
  crossref  = {DBLP:conf/wsfm/2006},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Further Readings:

Ellis, Rozenberg: Dynamic Change Within Workflow Systems
Ellis, El-khadiri: Flex-Flow: A Language and System for Flexible Workflow
Heinl: Exceptions during Workflow Execution
Jablonski: MOBILE: A Modular Workflow Model and Architecture
Jablonski, Stein, Teschke: Experiences in Workflow Management for Scientific Computing
Sadiq, Sadiq, Orlowska: Specification and validation of process constraints for flexible workflows
D.Giannakopoulou, K.Havelund: Automata-Based Verification of Temporal Properties on Running Programs
Dumas, v.d.Aalst, ter Hofstede: Process-Aware Information Systems