A framework for distributed synthesis of programs from input-output examples

Program synthesis is the task of automatically finding a program in an underlying Domain-Specific Language (DSL) that satisfies a specification provided by the user. In recent years the topics of program synthesis and in particular programming-by-example (PBE), a branch of program synthesis that uses input-output examples as specification, have gained significant traction, also thanks to the use of PBE tools in commercial applications, such as Excel'sFlashFill. Program synthesis is often considered as a difficult search problem, and one of the main focus of synthesis algorithms is to reduce and efficiently explore the search space. In addition to these techniques some synthesizers parallelize the search to improve performance, but the benefits of this optimization is still severely limited. In this thesis I explore the possibility of using distributed systems to further improve the performance of synthesis algorithms by increasing the number of parallel searches. I introduce an algorithm for PBE that aims to efficiently parallelize the search over a distributed system and implement it into a framework, then analyze the performance of the framework and which characteristics influence the effectiveness of distributed synthesis using instantiations for the string transformation and SQL domains. The evaluation of these instantiations on existing benchmarks shows that the developed algorithm allows performance comparable to that of current state-of-the-art techniques when used in a serial manner, and can also obtain a speedup of over 3x by using 5 parallel searches over a small distributed system.