The Application of Graph Theory to the Synthesis of Protocol Converters via the Interface Equation

Pengelly, Alan David (1995). The Application of Graph Theory to the Synthesis of Protocol Converters via the Interface Equation. PhD thesis The Open University.



The synthesis and subsequent generation of protocol converters can be a time consuming and tedious affair. An automatic means of generating these converters, given a formal description of the interfacing protocols, has been researched by a number of academics and industrialists. From industry's point of view, the potential gains both in time and resource savings are large. While there is a strong standards movement within the protocol community, the output from that process is likely to be slow in terms of its dissemination to the communications world at large. The recent emergence of the Superhighway has compounded the problems of standardisation. Hence, the development of converters will be a key issue for many years to come.

By far the most concise and complete attack on the problem to date came form a body of work referred to as the interface equation. While more general than other methods it has suffered from excessive computational complexity and, as with all other published work, a lack of demonstrable scalability. Also, the necessary and sufficient conditions before a solution could be found - if it existed at all - limited the domain of applicability.

The work in this thesis can be seen as a natural extension of this work, in that the problems of computability, scalability and a number of other issues, have been addressed, albeit by different approach.

The theory developed arose from a completely novel approach - moving the problem into the domain of graph theory and topology. The resulting theory has spawned a number of interesting results, which include extensions to CCS, further development of the quotient machine concept, the notion of symmetric validation and a further unification between automata and graph theory. Indeed, it is expected that the merging of these two disciplines may well open a rich field of study.

The theory has been validated using numerous examples, including a complex 600 state synthesis problem which, while still falling short of real industrial problems, is at least 1.5 orders of magnitude larger than those published by other researchers.

Viewing alternatives

Download history


Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions