CS628: Introduction to Asynchronous Systems
(Spring 2004)

Instructor Supratik Chakraborty
Friendly TAs Joycee Mekie Sayed Imranali Hafizali Abhijit Toley


All scores and grades have been posted. Happy vacations!

Course Description

This course aims at providing students with an understanding of the theory and practice of specifying, designing and verifying asynchronous systems. The primary purpose is to dispel the notion that asynchronous/concurrent systems are so complex that they are not worth dealing with, and to equip students with the background necessary for systematically reasoning about systems (software or hardware) in which concurrent components interact without global synchronization. At the end of the course, students should be able to understand the pros and cons of synchronous versus asynchronous implementations of a system, and be able to systematically design and analyze such systems.

Tentative Syllabus

The extent of coverage of topics in the syllabus will depend on the pace at which the course progresses.


Undergraduate knowledge of switching logic, automata theory, formal logic systems, algorithms.

Online resources


What When Where
LecturesThurs 17:00-18:00,
Fri 17:00-19:00
Seminar Hall, CSE Bldg.
Office hourWed 15:00-16:00
by email appointment
CFDVS (Maths Bldg Basement)

Tutorials When Where
Tutorial 1 Fri Jan 30, 17:00-19:00 CSE Seminar Hall
Tutorial 2 Fri April 2, 8:30-9:25 CSE Seminar Hall
Tutorial 3 Tue April 6, 18:30-19:30 CSE Seminar Hall
Tutorial 4 Tue April 13, 18:30-19:30 CSE Seminar Hall


Quizzes + assignments 30%
Endterm 50%
Group project 20%

Some more logistics ...

  • There will be no midterm examination.
  • Endterm exam and quizzes will be open book, notes and any material brought to the exam hall.
  • Assignments are due in class one week after they are given. No late turn-ins will be accepted, except under special and convincing circumstances.
  • If you miss a quiz for a genuine reason, meet the instructor after setting up an appointment.
  • Discussion among students for the purpose of clarification is strongly encouraged.
  • There will be zero tolerance for dishonest means like copying solutions from others in quizzes, assignments, end-term exam and in the group project. Anybody found indulging in such activities will be summarily awarded an FR grade. The onus will be on the supposed offender to prove his or her innocence.

Quizzes, Assignments, Practice Problems, Exams ...

Homework 1 Due Feb 13, 2004
Quiz 1 Mar 9, 2004
Homework 2 Due Mar 26, 2004
Quiz 2 April 2, 2004
Homework 3 Due April 17, 2004
Quiz 3 April 20, 2004
End Sem 2001 paper (For practice only)
End Sem 2002 paper (For practice only)
End Sem 2003 paper (For practice only)

Group Projects

Reading Material


  • Papers and articles to be announced in class.
  • Class notes.

Current Reading List

  1. Selected sections (dealing with topics covered in class) from Petri nets: Properties, analysis and applications , T. Murata, pp. 541-580 in "Proceedings of the IEEE", Vol 77, No. 4, April 1989 (available in Central Library).
  2. Programming in VLSI: From Concurrent Processes to Delay-Insensitive Circuits, A. J. Martin, pp 1-64 in "Developments in Concurrency and Communication", Addison Wesley, 1997 (available in Central Library).
  3. Class lecture notes on specification and synthesis using STGs, and algorithm for solving CSC conflicts.
  4. Selected sections from A Region Based Theory for State Assignment in Speed-Independent Circuits, J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, A. Kondratyev, pp. 793-812, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 16, No. 8, Aug 1997. [PDF]
  5. Selected chapters (Chapter 3 -- in particular, sections 3.3.2, 3.3.3 and 3.3.4 -- and Chapter 4) from Luciano Lavagno's impressive Ph.D. thesis for more on STG based synthesis.
  6. Ivan Sutherland's seminal paper on Micropipelines [PDF]
  7. Class lecture notes on CTL, LTL and verification using model checking.
  8. Selected sections from Alur and Dill's paper on A Theory of Timed Automata . [Postscript].
    You need to read from pages 4 to 11 of Alur and Dill's paper to understand the nuts and bolts of timed automata. You may go through the introductory material in pages 1-3 to get some perspective, but this is not necessary if you're short on time. Also look at the nice example given on Page 13 (Example 3.16).
  9. Chapter on Temporal Logics in the book "Model Checking", by Edmund Clarke Jr., Orna Grumberg and Doron Peled, The MIT Press (pages 27-31).

References for the more interested ...

  • Asynchronous Circuit Design,   Chris J. Myers   John Wiley and Sons
  • Asynchronous Sequential Switching Circuits,   Stephen Unger   Wiley-Interscience, New York
  • Communicating Sequential Processes,   C.A.R. Hoare   Prentice Hall International Series in Computer Science
  • The Theory and Practice of Concurrency,   A. W. Roscoe   Prentice Hall International Series in Computer Science
  • Proceedings of the IEEE - Special Issue on Asynchronous Circuits and Systems,   Feb 1999
  • Hardware Design and Petri Nets,   A. Yakovlev, L. Gomes and L. Lavagno   Kluwer Academic Publishers
  • Concurrent Hardware: The Theory and Practice of Self-Timed Design,   A. Kondratyev, A. Taubin and V. Varshavsky   John Wiley and Sons

Lecture Schedule

DateTopics details
Dec 30Introduction, basic notion of synchronous and asynchronous systems; globally synchronized views of time. Notion of a system and its environment. Delay models: delay insensitive, quasi-delay insensitive, speed independent and timed systmes
Jan 2Small examples of delay insensitive, quasi-delay insensitive and timed systems. Petri Nets as a mechanism of specifying behaviour at the interface between a system and its environment. Petri Net basics: definition, markings, rules for transition firing, mathematical notation. Representing concurrency, synchronization, choice/conflict, sequencing, merge of events using Petri Nets. k-safeness and 1-safeness of Petri Nets
Jan 8Talk by Prof. Jordi Cortadella. Trace set of a Petri Net. More on equivalence of k-safe and 1-safe Petri Nets
Jan 9Petri Nets: free choice, extended free choice, liveness. 1-safe Petri Nets and state transition diagrams: comparison of benefits of each formalism. Going from Petri Nets to state transition diagrams and vice versa. Introduction to a CSP-based process algebra: syntax and semantics. Finite and infinite processes. Sequential composition, non-deterministic choice, guarded actions, tail recursion for defining infinite processes
Jan 15 Institute holiday
Jan 16More of process algebra syntax and semantics: parallel or concurrent composition. Expressive equivalence of process algebra described and Petri Nets. Converting Petri Nets to process algebraic descriptions and vice versa. Example of a scalable queue described using process algebraic constructs.
Jan 22Handshakes as a mechanism of communication: two and four-phase handshakes. Notion of channels, ports, active and passive handshakes. Martin's CHP description of processes; their handshaking expansion. Effect of placing handshaking actions at different points in a sequence of handshakes. Example of a sequencer process with a passive L port and two active R (R1, R2) ports: its CHP description.
Jan 23Expansion of CHP of description of sequencer into 2-phase handshakes. Production rules (PR): definition, identifying PRs from a handshaking expansion, naive implementation from PRs. Implementation of sequencer and its environment using wires (buffers) and a negation gate. 4-phase handshaking expansion of sequencer CHP description; obtaining PRs from this expansion. Stability and non-interference of PRs. Interference among PRs obtained from 4-phase handshaking expansion of the sequencer. Reshuffling of handshaking actions, and how it helps remove some of the interference between PRs.
Jan 29Further reshuffling of 4-phase handshaking events of sequencer. Illustration of how reshuffling can help yield simpler designs. Strongest precondition of an event in a process description. Mutually exclusive strongest preconditions. Deriving stable guards (strongest guards) from strongest preconditions.
Jan 30Tutorial 1: Toggle and Merge elements. Combining Toggle and Merge elements to obtain a 2-phase to 4-phase (or vice versa) handshake converter.
Feb 5Combining strongest preconditions of same event (action) occurring at different points in a process description. Mutually exclusive strongest preconditions: necessary and sufficient conditions for existence of a stable PR set. Deriving strongest and weakest guards of an event.
Feb 6Simplifying strongest guards of PRs using don't-care sets from process description. Illustration with simple sequencer having 4-phase handshakes. Strengthening weakest guards of PRs by inspection, while ensuring that there are no conflicting assignments to the same variable/port. Symmetrization of guards enabling assignment of conflicting values to same variable/port. Illustration with simple sequencer.
Feb 12Decomposition of a process into an interconnection of linear processes using specialized elements like Merge, C-element (synchronizer), Arbiter. Notion of waking up and going to sleep in the context of processes.
Feb 14More on decomposition of processes. Dealing with concurrency, synchronization, choice when decomposing a process. Simple examples illustrating how different process descriptions can lead to the same interconnection of basic elements.