A distributed algorithm for implementation of first-order multiparty interactions

First-order multiparty interactions, a generation of multiparty synchronization, are a powerful communication mechanism that allows a set of processes to enroll into different roles of an interaction and to execute the interaction in a synchronous way, and guarantees conflict interactions to be executed exclusively. It is not a trivial problem to implement first-order multiparty interactions in a network environment. The implementation has to maintain the synchronous and exclusive properties mentioned above, be fair and make progress. In this paper, we propose a new distributed algorithm for implementing first-order multiparty interactions based on a new implementation model, in which a role manager is devised for each role. Our algorithm solves the problem with O(|R|².|P|) messages per interaction as opposed to |P| ² messages required in Joung and Smolka (1994), where |R| is the number of roles of the interaction and |P| is the number of processes. Our algorithm is more efficient than that in Joung and Smolka, when |R|²<|P|. Furthermore our algorithm is closer to the fully distributed one in the sense that (1) every process (role manager) only knows its adjacent role managers (processes), and (2) the time complexity of local computation in each process and role manager is equal