Description of the course ELG 7187C (Winter 2013)

Professor: Gregor v. Bochmann , phone: 562-5800 ext.: 6205, e-mail: bochmann@site.uottawa.ca , office: SITE building (room 5082), office hours: to be determined

Lectures: Monday from 14:30 to 17:30 in SITE F 0126

Overview 

The course gives an introduction to methods for describing and analysing requirements and designs of reactive systems,  especially for distributed applications. The main application areas are telecommunication systems, IP telephony and teleconferencing, Internet applications, Web Services and workflow modeling. Because of their complexity, these systems are difficult to design and implement. The students will learn about the principal methods that can be used for the design of such systems, for the precise descriptions of requirements and designs, and for the verification of these descriptions and the corresponding implementations in terms of logical correctness, reliability and real-time response. At the same time, the students will use certain abstract models and specification languages and their associated tools that permit the automation of certain development steps.

The course gives an introduction to certain formal modelling concepts (labelled transition systems, communicating finite state machines, Petri nets), and certain specification languages and other notations (such as UML State and Activity diagrams, and interaction diagrams) and their use during the software development process using automated CASE tools. The course also deals with the comparison of different specifications based on various conformance relations, refinement, abstraction, module composition and replacement.

Emphasis is put on the requirement-driven development of distributed applications. This includes the derivation of the behavior of the different system components (communication protocol) from the given overall requirements of a distributed system, and the composition of a more complex system from several distributed subsystems providing some given features or functions. The orderly composition of such features is one of the most complex issues in the construction of complex real-time systems, sometimes referred to as "feature interactions". The course will also cover questions related to using existing infrastructures, such as CORBA, Java RMI and Web Services, for the implementation of the derived communication protocols.

Leaning objectives

The following list contains some high-level learning objectives for this course. Each objective is preceeded by references to the "graduate attribute criteria" to which they belong (see Section 3.1 of the CEAB Accreditation Criteria and Procedures). In addition, the chapters of the course that concentrate on the objective are indicated at the end.

1. (2-Analysis; 4-Design; 5-Tools) To design models of system behaviors that satisfy certain given requirements, using different modeling notations such as activity diagrams, labelled transition systems, finite state machines, input-output automata or Petri nets. (Chapters 1, 2)
2. (2-Analysis; 4-Design; 5-Tools) To design communication protocols for distributed systems that provide a global service that satisfies certain given requirements, using certain methods that are appropriate for the given situation. (Chapters 3, 7)
3. (2-Analysis; 5-Tools) To verify that a given communication protocol functions without flaws and provides a given required global service, possibly using automated tools for this purpose. (Chapters 3, 6)
4. (2-Analysis; 4-Design; 5-Tools) To use Markov models or Timed Automata to model the performance characteristics of a given functional behavior specifications, and to derive certain performance properties from these models. (Chapter 4)
5. (1-Knowledge) To understand how remote procedure calls and the conventions of Web Services can be used to build implementations of distributed system designs. (Chapter 5)

Course activities:

• Lectures and discussions.
• Small exercises to be prepared by the student.
• Student project, applying one of the design principles covered in the course to a relatively simple example system, and possibly using one of the existing software tools for this purpose. The student writes a report on his work and gives a short presentation of the results at the end of the course.

Reading material: Reading material will be provided in the form of course notes and articles from the literature

Prerequisites

• Programming (for instance in Java): interfaces, classes, threads, and how to program algorithms (see for instance in course SEG 2105 and 2106)
  
• UML: Class diagrams, collaboration and sequence diagrams (see for instance in course SEG 2105)
  
• Finite state machines and UML state diagrams (see for instance in course SEG 2106)
  
• Software engineering: development methods and processes (see for instance in course SEG 2105)
  

Course content  

1. Introduction: the software development process, behavioral modeling and CASE tools (1 week)
   • Waterfall and spiral software development processes - Model-Driven Architecture
   • Notations: programming languages, first-order logic, temporal logic, UML (Class, State, Activity diagrams), formal state-transition modeling (LTS, FSM, IOA, Petri nets); the nature of syntax and semantics - the need for formality
   • CASE tools: editing, verification, transformations, code generation, testing support
   • Different types of component interactions - interfaces (procedure call, messaging passing, rendezvous - local or remote)
   • Specification of component requirements including assumptions about the environment
   • The challenges of distributed applications
   • Historical notes about notations for defining requirements, models and implementations and associated tools - experience and future outlook
     
2. Behavior modeling using states and transitions (2 week)
   • Labelled transition systems (LTS) - nondeterminism
   • State spaces defined by variables: guarded commands or first-order logic specifications
   • Petri nets
   • State machines with inputs and outputs (IOA, FSM) - the alternating bit protocol example
   • Extended state machines and extended Petri nets (and relationship to practical modeling notations, such as SDL, UML State Diagrams, UML Activity Diagrams)
   • Example systems
3. Distributed system design (2 week)
   • Composition and reachability analysis - design flaws (for different communication paradigms: rendezvous, instantaneous events, message passing, procedure call)
   • Tools
   • Gouda's method for avoiding protocol design flaws
   • Communication services and their interconnection through gateways
   • Examples of distributed applications
4. Performance modeling (1 week)
   • Overview of principal modeling approaches
   • Timed automata
5. Applications: Web Services and workflow modeling (1 week)
   • Remote procedure calls (CORBA, Java RMI, SOAP)
   • Introduction to XML, XSL, schemas, etc.
   • Web Services, BPEL, and other notations
   • Transaction management
6. Comparing specifications and model checking (1 week)
   • Abstraction by projection (hiding interfaces) - state-nondeterminism
   • Different criteria for comparing specifications (trace semantics, refusal semantics, etc.) - safeness, liveness, progress etc.
   • Temporal logic and model checking
7. Deriving protocols for communication services and distributed workflow applications (2 week)
   • Partial order relations - weak and strong sequencing
   • Finding message passing protocols for realizing distributed behaviors involving strong sequencing
   • Describing complex distributed behaviors as a composition of simpler collaborations
   • Finding message passing protocols for complex behaviors involving weak sequencing
   • Tools - applications
     
8. Future perspective
   
9. Project presentations by students (2 weeks, estimated)
   

Last updated: December 10, 2012