Top-Down or Bottom-Up? Complexity Analyses of Synchronous Multiparty Session Types

Explore a 22-minute conference talk from POPL 2025 that compares the complexity of two main approaches in multiparty session types (MPST): top-down and bottom-up. Presented by Thien Udomsrirungruang and Nobuko Yoshida from the University of Oxford, the talk analyzes which approach is more efficient for ensuring communication safety, deadlock-freedom, and liveness in concurrent systems. Learn about their novel algorithms using graph representation of session types, including a quadratic subtyping system that improves upon existing exponential algorithms, a PSPACE-algorithm for coinductive projection with full merging, and a new type inference system generating minimum type graphs. The presentation reveals that top-down approaches based on global types are often more efficient than bottom-up methods in realistic scenarios, with liveness checking in bottom-up approaches having the highest complexity. The research also demonstrates that type inference costs grow exponentially with process size, significantly impacting overall complexity.