Distributed Match-Making

Sape J. Mullender, Paul M.B. Vitanyi

    Research output: Contribution to journalArticleAcademicpeer-review

    57 Downloads (Pure)

    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 data management involve making matches between such processes. We propose a formal 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.
    Original languageUndefined
    Pages (from-to)367-391
    Number of pages25
    JournalAlgorithmica
    Volume3
    Issue number3
    DOIs
    Publication statusPublished - 1988

    Keywords

    • IR-55888
    • EWI-1246

    Cite this

    Mullender, S. J., & Vitanyi, P. M. B. (1988). Distributed Match-Making. Algorithmica, 3(3), 367-391. https://doi.org/10.1007/BF01762123