Link Search Menu Expand Document

The 11th IFIP WG 1.8 Workshop on Trends in Concurrency Theory

September 12, 2022, Warsaw, Poland

A satellite event of CONFEST 2022

Description

TRENDS 2022 is an event organised by IFIP WG 1.8 on Concurrency Theory. It aims at bringing together researchers interested in Concurrency Theory and its applications, to exchange ideas and discuss recent trends and open problems. The event will take place on September 12, 2022. It will be associated with the yearly WG 1.8 business meeting.

Invited Speakers

  • Javier Esparza, Technische Universität München, DE

    Title: State Complexity of Population Protocols

    Population protocols were introduced by Angluin et al. in 2004 to study the theoretical properties of networks of mobile sensors with very limited computational resources. They have also been proposed as a natural computing model, with molecules, cells, or microorganisms playing the role of sensors.

    In a population protocol an arbitrary number of indistinguishable, finite-state agents interact randomly in pairs to collectively decide if their initial global configuration satisfies a given property. The property is formalized as a predicate that maps each initial configuration to an output, 0 or 1. Starting from an initial configuration, the agents eventually agree to the correct output almost surely, and continue producing it forever. The protocol is said to stabilize to the correct output.

    It is well known that population protocols can decide exactly the semilinear predicates, or, equivalently, the predicates expressible in Presburger arithmetic. Current research concentrates on investigating the amount of resources needed to decide a given predicate. The standard resources, time and memory, translate for population protocols into expected time to stabilization, usually called parallel runtime, and number of states of each agent. In this talk I present upper and lower bounds for the state complexity of population protocols.

  • Kirstin Peters, Augsburg University, DE

    Title: Multiparty Session Types for Distributed Algorithms

    Multiparty session types are designed to abstractly capture the structure of communication protocols and verify behavioural properties. Distributed algorithms were originally not in the focus of multiparty session types, but their resemblance with communication protocols inspired attempts to use multiparty session types for the verification of distributed algorithms.

    This talk briefly discusses the challenges in applying multiparty session types on distributed algorithms. Some of these challenges were already tackled in recent research papers, while other challenges are still open problems.

  • Stefan Kiefer, University of Oxford, UK

    Title: Strategies in Countable MDPs

    Markov decision processes (MDPs) are a standard model for dynamic systems that exhibit both stochastic and nondeterministic behavior. For MDPs with finite state space it is known that for a wide range of objectives there exist optimal strategies that are memoryless and deterministic. In contrast, if the state space is infinite, optimal strategies may not exist, and optimal or epsilon-optimal strategies may require (possibly infinite) memory. This gives rise to a reach landscape of strategy complexity: how much memory is required, in the worst case, to play optimally or epsilon-optimally? In this talk we discuss strategies with optimal strategy complexity for countable MDPs, building on strategies for finite MDPs. We focus on qualitative objectives such as reachability, safety, (co-)Büchi, and other parity objectives.

    Joint work with Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke, Dominik Wojtczak.

Programme

8:50-9:00 - Opening

9:00-10:00 - Kirstin Peters. “Multiparty Session Types for Distributed Algorithms”

10:00-10:30 - Coffee break

10:30-11:30 - Stefan Kiefer. “Strategies in Countable MDPs”

11:30-12:30 - Javier Esparza. “State Complexity of Population Protocols”

12:30-14:30 - Lunch break

14:30-15:30 - IFIP WG 1.8. business meeting

15:30-16:00 - Coffee break

Participation

Participation, both to the workshop and to the IFIP WG 1.8 meeting, is open to everybody. For registration, please consult the CONFEST 2021 registration page.

Organizers

Pedro R. D’Argenio (Universidad Nacional de Córdoba, Argentina)

Ana Sokolova (University of Salzburg, Austria)

IFIP WG 1.8 on Concurrency Theory

The aims of IFIP WG 1.8 on Concurrency Theory are:

  • To develop theoretical foundations of concurrency, exploring frontiers of existing theoretical models like process algebra and process calculi, so as to obtain a deeper theoretical understanding of concurrent and parallel systems.

  • To promote and coordinate the exchange of information on concurrency theory, by sharing ideas, discussing open problems, and identifying future directions of research in the area.

The activities of this WG encompass all aspects of concurrency theory and its applications.

More information on IFIP WG 1.8 can be found on its home page.

History

The first instalment of TRENDS (TRENDS 2012) was held on September 8, 2012 as a satellite event of CONCUR 2012, in Newcastle upon Tyne, UK.

The second instalment of TRENDS (TRENDS 2013) was held on August 31, 2013 as a satellite event of CONCUR 2013, in Buenos Aires, Argentina.

The third instalment of TRENDS (TRENDS 2014) was held on September 6, 2014 as a satellite event of CONCUR 2014, in Rome, Italy.

The fourth instalment of TRENDS (TRENDS 2015) was held on September 6, 2015 as a satellite event of CONCUR 2015, in Madrid, Spain.

The fifth instalment of TRENDS (TRENDS 2016) was held on August 27, 2016 as a satellite event of CONCUR 2016, in Quebec City, Canada.

The sixth instalment of TRENDS (TRENDS 2017) was held on September 9, 2017 as a satellite event of CONCUR 2017, in Berlin, Germany

The seventh instalment of TRENDS (TRENDS 2018) was held on September 8, 2018 as a satellite event of CONCUR 2018, in Beijing, China

The eighth instalment of TRENDS (TRENDS 2019) was held on August 31, 2019 as a satellite event of CONCUR 2019, in Amsterdam, The Netherlands

The ninth instalment of TRENDS (TRENDS 2020) was held on September 5, 2020 as a satellite event of CONCUR 2020, in Vienna, Austria Online

The tenth instalment of TRENDS (TRENDS 2021) was held on August 28, 2021 as a satellite event of CONCUR 2021, in Paris, France Online