1988 Springer-Verlag New York Inc. Distributed Match-Making t

Abstract. In many distributed computing environments, processes are concurrently executed by nodes in a store-and-forward communication network. Distributed control issues as diverse as name server, mutual exclusion, and replicated ata management i volve making matches between such processes. We propose aformal problem called "distributed match-making " as the generic paradigm. Algorithms for distributed match-making are developed and the complexity is investigated in terms of messages and in terms of storage needed. Lower bounds on the complexity of distributed match-making are established. Optimal algorithms, or nearly optimal algorithms, are given for particular network topologies