Team Formation and Applications
For researchers in distributed computing, this work provides a new primitive that simplifies the solution of various fundamental problems, though the results are incremental in nature.
The paper introduces a new distributed problem called Team Formation (TF) and presents a randomized algorithm that is efficient in both messages and time. It shows that TF can serve as a building block for many other distributed problems, achieving the first linear message complexity for asynchronous implicit leader election and improving time complexity for explicit leader election.
A novel long-lived distributed problem, called Team Formation (TF), is introduced together with a message- and time-efficient randomized algorithm. The problem is defined over the asynchronous model with a complete communication graph, using bounded size messages, where a certain fraction of the nodes may experience a generalized, strictly stronger, version of initial failures. The goal of a TF algorithm is to assemble tokens injected by the environment, in a distributed manner, into teams of size $σ$, where $σ$ is a parameter of the problem. The usefulness of TF is demonstrated by using it to derive efficient algorithms for many distributed problems. Specifically, we show that various (one-shot as well as long-lived) distributed problems reduce to TF. This includes well-known (and extensively studied) distributed problems such as several versions of leader election and threshold detection. For example, we are the first to break the linear message complexity bound for asynchronous implicit leader election. We also improve the time complexity of message-optimal algorithms for asynchronous explicit leader election. Other distributed problems that reduce to TF are new ones, including matching players in online gaming platforms, a generalization of gathering, constructing a perfect matching in an induced subgraph of the complete graph, quorum sensing in message-passing networks, and more. To complement our positive contribution, we establish a tight lower bound on the message complexity of TF algorithms.