An Efficient Distributed Algorithm for Implementation of Multi-Rendezvous based on l-Chain-Coterie

摘要

Multi-Rendezvous is a powerful communication mechanism that allows a group of processes to execute an event in a synchronous way. Besides the multisyrnchronous property Multi- Rendezvous has an exclusive property which requires no more than one group to execute their events simultaneously, if they share a common process. It is not a trivial task to implement Multi-Rendezvous in a network system The implementation has to maintain the properties mentioned above, be fair and make progress. Some highly abstract specification languages have employed Multi-Relldezvous to enhance the specification power of the languages, e.g., LOTOS, a specification language for communication protocols and distributed systems. Coterie is a communication structure which has been used in solutions for many distributed problems such as mutual exclusion, replica control, and distributed consensus. Our previous work has shown that coterie can also be used for solving implementation problem of Multi-Rendezvous, with O(N~1.5 ) message passes. In this paper, we propose a communication structure called l-chain-coterie, as a generalization of coterie, and a more efficient distributed algorithm for implementing Multi-Rendezvous based on the structure with O(N~l+1l/l) message passes. Our algorithm is fully distributed and does not use manager processes and auxiliary resources.