Concurrency Theory

---

Course Description

---

Notes

Foundations

• Motivation for Concurrency Theory (from concurrent prog course)
• Concurrency via Sharing Events
• Distributed Alphabet
  • Direct Product Automata
  • Shuffle Closure
  • Direct Product Automata are not closed under boolean operations
• Trace
  • Trace Closure is not the same as Shuffle Closure
• Synchronous Automata
  • Synchronous Languages are finite union of direct product languages
• Asynchronous Automata
  • Not all regular trace languages are synchornous

Zielonka’s Theorem

• Gossip Automata
  • Gossip Problem
  • Gossip Automata can be implemented as Asynchronous Automata
  • The maximal elements of view of 2 processes is in the primary of both processes
• Trace Independence is a Syntactic Congruence of Trace Languages
• Zielonka’s Theorem
• Loc Past PDL

Synchronous Distributed Games

• Flip Flop
• Synchronous Distributed Games
• Information Pre-Order
  • Information Chains
• Solving Synchronous Distributed Games

---

MOCs

• Concurrent Programming
• Algebraic Automata Theory

---

Practical Information

Prof : C. Aiswarya Timings : 9:10 am - 10:25 am on Wednesday and Monday Loc : 801

---

References