The Game of Concurrency : Strategy Synthesis For the Concurrent Program Problem Through Application of Multi-agent Games of Imperfect Information

Sammanfattning

In programming, a concurrent program is a program that divides a task into smaller subprograms (typically referred to as threads), which are then executed concurrently. This allows for the program to take advantage of the computer hardware and complete its task as quickly as possible. However, this approach is not without its flaws. The most common problems involve threads finishing its task quicker or slower than expected, and thus causing unexpected behavior, resulting in a program crash or incorrect output. This is usually caused by a lack of information and communication within the program. It is therefore interesting for computer scientists to determine a strategy to reduce or eliminate the risk of this happening. In this report, we investigate the concurrent program problem with the help of game theory models and algorithms. We model a sample concurrent program, written in Go, according to the model Multi-agent Games with Imperfect Information Against Nature (MAGIIAN). We then attempt to synthesize a winning strategy for the resulting model by applying the algorithm Multiplayer Knowledge-based Subset Construction (MKBSC), utilizing an existing tool to do this automatically. Due to technical limitations of this tool, a simplified variant of the model is devised for compatibility. Finally, we compare the synthesized strategy to a human-intuitive strategy we came up with on our own, to see whether we can produce a more efficient strategy with the help of game theory. In conclusion, we found that the synthesized strategy for the simplified model did not differ from our intuitive strategy. Thus, further development of the tool we used to resolve its limitations is suggested in order to build upon our findings in this thesis.