Diameter of multithreaded programs

Explore the asymptotic diameter of finite-state multithreaded programs.

• Tutors: Alexander Malkis
• Degree: bachelor | master | research paper
• State: open

Given: the set of all multithreaded programs with finite state space.

Prove or find a counterexample: the asymptotic diameter of transition systems of such programs cannot grow exponentially in the number of threads if the shared state space and local state spaces have constant size.