Скачать или смотреть STEP21jun23RossHorne

Ross Horne: Assuming Just Enough Fairness to make Session Types Complete for Lock-freedom
Аннотация: Over the past couple of decades we, as a community, have been exploring behavioural properties that session types guarantee. We mainly agree that session types should guarantee deadlock-freedom; and, when there are three or more parties, better still, we target a finer property such as lock-freedom, which ensures that whenever a participant wants to do something they eventually will. Lock-freedom is more difficult to define precisely than deadlock-freedom, not least because it is sensitive to the precise notion of fairness we assume.
Recently, I made the observation that assuming a minimal realistic notion of fairness called "justness", developed by my co-authors Peter Höfner and Rob van Glabbeek, leads to a notion of lock-freedom that tightly matches session types. After investigating this observation we determined that, in fact, the resulting notion of "just lock-freedom" is complete​ for session types. This was a surprise for me and appears to be the first such completeness result for session type systems: that is, if you directly model check the behavioural property "just lock-freedom", then you can always synthesize a global type for that session. This result is surprisingly sensitive to the fine details of (1) the definition of the operational semantics of sessions, (2) the precise definition of projection from global types to local types, and (3) the precise formulation of lock-freedom, as well as (4) the fairness assumption. The design decisions we made to achieve completeness were informed by a systematic investigation where we took into account all possible notions of fairness.
(There is a 15min video introducing this problem: https://satoss.uni.lu/members/ross/pd...)