Distributed match-making
There are many different issues in distributed control, e.g., name server, mutual exclusion, replicated data management, etc. In this paper, the coordination of interrelated processes (and nodes) is considered as the ``heart of distributed control and a simple theoretical problem, distributed match-making is proposed as the generic paradigm of studying distributed control. Intuitively, the distributed match-making problem is to assign a rendezvous (node) for each pair of nodes in the network. Two complexity measures are defined: communication complexity and storage complexity. Communication represents the average number of messages that need to be sent in order for a pair of nodes to make a match (i.e., both of them send messages to their rendezvous) and storage represents the average (or worst-case) amount of cache memory needed in a node for storing match-making messages. We want to minimize communication as well as storage. An interesting relation between the communication and the distributedness (i.e., how distributed the rendezvous are in the network) of a distributed match-making strategy is obtained. It is shown that communication increases as distributedness increases. A nice trade-off between communication and storage is presented. The result implies that it is impossible to minimize both communication and storage at the same time. These complexity results give theoretical limitations to the efficiency of solutions for many practical problems in this area. As an example, the coordination problems in practical distributed control issues such as name server, mutual exclusion and replicated data management are formalized as distributed match-making problems. Simple (optimal and nearly optimal) algorithms for distributed match-making in networks with various topologies are also exhibited. Several future research issues such as probabilistic algorithms, hashing method, and fault-tolerance are discussed at the conclusion of the paper. With many simple mathematical proofs and examples, the paper is very easy to read.
- A Scheme for Fast Parallel Communication
- scientific article; zbMATH DE number 4096767 (Why is no real title available?)
- scientific article; zbMATH DE number 3448641 (Why is no real title available?)
- scientific article; zbMATH DE number 3333196 (Why is no real title available?)
- Reverse path forwarding of broadcast packets
- The mutual exclusion problem
- Arbitrated matching: Formulation and protocol
- Planar quorums
- Randomized leader election
- Optimal availability quorum systems: theory and practice
- Distributed Stable Matching Problems
- scientific article; zbMATH DE number 4062556 (Why is no real title available?)
- A note on weighted distributed match-making
- Construction of optimal communication structures for weighted distributed match-making
- Local distributed agent matchmaking
- Load balancing in quorum systems
- Crumbling walls: a class of practical and efficient quorum systems
- Synchronous Byzantine quorum systems
- Compact and localized distributed data structures
- Planar quorums
- The availability of crumbling wall quorum systems
- A class of deadlock-free Maekawa-type algorithms for mutual exclusion in distributed systems
- Resource finding in store-and-forward networks
- Linear election in pancake graphs
This page was built for publication: Distributed match-making
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107317)