Distributed Match-Making

Sape J. Mullender, Paul M.B. Vitanyi

    Research output: Contribution to journalArticleAcademicpeer-review

    44 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
    Mullender, Sape J. ; Vitanyi, Paul M.B. / Distributed Match-Making. In: Algorithmica. 1988 ; Vol. 3, No. 3. pp. 367-391.
    @article{593b82dd5ca14113a1319c1cb4ed3d59,
    title = "Distributed Match-Making",
    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.",
    keywords = "IR-55888, EWI-1246",
    author = "Mullender, {Sape J.} and Vitanyi, {Paul M.B.}",
    note = "Imported from DIES",
    year = "1988",
    doi = "10.1007/BF01762123",
    language = "Undefined",
    volume = "3",
    pages = "367--391",
    journal = "Algorithmica",
    issn = "0178-4617",
    publisher = "Springer",
    number = "3",

    }

    Mullender, SJ & Vitanyi, PMB 1988, 'Distributed Match-Making' Algorithmica, vol. 3, no. 3, pp. 367-391. https://doi.org/10.1007/BF01762123

    Distributed Match-Making. / Mullender, Sape J.; Vitanyi, Paul M.B.

    In: Algorithmica, Vol. 3, No. 3, 1988, p. 367-391.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Distributed Match-Making

    AU - Mullender, Sape J.

    AU - Vitanyi, Paul M.B.

    N1 - Imported from DIES

    PY - 1988

    Y1 - 1988

    N2 - 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.

    AB - 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.

    KW - IR-55888

    KW - EWI-1246

    U2 - 10.1007/BF01762123

    DO - 10.1007/BF01762123

    M3 - Article

    VL - 3

    SP - 367

    EP - 391

    JO - Algorithmica

    JF - Algorithmica

    SN - 0178-4617

    IS - 3

    ER -

    Mullender SJ, Vitanyi PMB. Distributed Match-Making. Algorithmica. 1988;3(3):367-391. https://doi.org/10.1007/BF01762123