Alladi Ramakrishnan Hall

Some Decidable Classes of the Distributed Synthesis Problem

Anup Basil Mathew

IMSc

*** This is the Public Viva Voce Examination of Anup's Ph D Thesis submission. ***

The distributed synthesis problem (or DSP) is the
following: Given an architecture and a property as input, find a distributed system on the architecture that satisfies the given property.

It is known that DSP is undecidable even for 'simple' input-classes, but some input-classes that admit a decidable DSP have also been identified. In this thesis, we identify more input-classes with decidable DSP.

The results are summarized below:

1. We show that on inputs that admit the property of recurring common knowledge of state", DSP reduces to the winning strategy problem on perfect information game-graphs, which is a known decidable problem.

2. We consider several input-classes, some of which are from the literature, and give a uniform argument for their decidability. The idea can be summarized as follows: first, we define a structure called
a "witness" that witnesses a distributed system associated with an input; second, for each input-class being considered, we show that the witnesses
associated with an input admit a transformation to bounded-size witnesses,
and decidability follows from this.