[FM-India]IARCS Verification Seminar Series -- Talk by Krishna S on Dec. 6 at 1900 hrs IST

Dear all, The next talk in the IARCS Verification Seminar Series will be given by Krishna S, a faculty member in the Department of Computer Science and Engineering at IIT Bombay. The talk is scheduled on Tuesday, December 6, at 1900 hrs IST (add to Google calendar <https://calendar.google.com/calendar/event?action=TEMPLATE&tmeid=MWU1amtjNGUwdm5mcTZvZ242dXFqZ3UwNDMgdnNzLmlhcmNzQG0&tmsrc=vss.iarcs%40gmail.com> ). The details of the talk can be found on our webpage ( https://fmindia.cmi.ac.in/vss/), and also appended to the body of this email. The Verification Seminar Series, an initiative by the Indian Association for Research in Computing Science (IARCS), is a monthly, online talk-series, broadly in the area of Formal Methods and Programming Languages, with applications in Verification and Synthesis. The aim of this talk-series is to provide a platform for Formal Methods researchers to interact regularly. In addition, we hope that it will make it easier for researchers to explore newer problems/areas and collaborate on them, and for younger researchers to start working in these areas. All are welcome to join. Best regards, Akash, Deepak, Madhukar, Srivathsan ============================================================= Title: Verification of Concurrent Programs under Release Acquire Meeting Link: https://us02web.zoom.us/j/89164094870?pwd=eUFNRWp0bHYxRVpwVVNoVUdHU0djQT09 (Meeting ID: 891 6409 4870, Passcode: 082194) Abstract: This is an overview of some recent work on the verification of concurrent programs. Traditionally concurrent programs are interpreted under sequential consistency (SC). Eventhough SC is very intuitive and easy to use, modern multiprocessors do not employ SC for performance reasons, and instead use so called "weak memory models". Some of the well known weak memory models in vogue among modern multiprocessor architectures are Intel x-86, IBM POWER and ARM. The use of weak memory is also prevalent in the C11 model, leading to the release acquire fragment of C11. This talk is on the verification of concurrent programs under the release acquire (RA) semantics. The main focus of the talk will be on non parameterized programs under RA, and I will briefly discuss results in the parameterized setting. In the non parameterized setting, we show that the reachability problem for RA is undecidable even in the case where the input program is finite-state, closing a long standing open problem. What works well for this class is under approximate reachability, in the form of bounded view switching, an analogue of bounded context switching, relevant to RA. In the parameterized setting, the first observation is that the semantics of RA can be simplified, lending to a better complexity for verification. Further, safety verification is PSPACE-complete for the case where the distinguished threads are loop-free, and jumps to NEXPTIME-complete for the setting where an unrestricted distinguished ego thread interacts with the environment threads. This talk is based on papers that appeared in PLDI'19 (joint with Parosh Abdulla, Mohamed Faouzi Atig and Jatin Arora), PODC'22 (joint with Roland Meyer and Adwait Godbole) as well as some unpublished work. Bio: Krishna S is a faculty member in the Department of Computer Science and Engineering at IIT Bombay. Her areas of research are broadly in Automata, Logics, Games and the formal verification of timed and probabilistic systems.