Construction of Deadlock-free Designs of Communication Protocols from Observations

Reverse engineering in distributed systems is essential to recovering the designs of large and complex distributed systems that evolve often without proper documentation. This paper proposes rules for the automated construction of deadlock-free designs of communication protocols from the execution histories of existing systems, defines the properties of the constructed designs and identifies the conditions for a constructed design to be equivalent to the presumed design implied by the given set of global observations.