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