Team Formation and Applications

We introduce a long-lived distributed problem called team formation (TF), defined over an integral team size parameter $2\le \sigma \le n$.⁴⁴4The TF problem is well defined also for $\sigma >n$, however, the restriction to $\sigma \le n$ simplifies the discussion and is consistent with the applications presented in Sec. 1.4. In a TF instance, abstract tokens are injected into the nodes over time, where the adversary determines the timing and location of these token injections. Tokens held by a node $v\in V$ can be transported to a node $v^{\prime }\in V$ over a message sent from $v$ to $v^{\prime }$. Each token remains in the system until it is deleted, as explained below.

The correctness criterion of the TF problem is captured by the following two conditions:

Safety:

a token can be deleted from the system only as part of a team that consists of exactly $\sigma$ tokens, all of which are held by the same node and deleted simultaneously; the operation of deleting a team of tokens is referred to as forming a team.

Liveness:

if the system contains at least $\sigma$ tokens, then a team must be formed in a finite time.

Assume without loss of generality that the system contains at most $n^{O(1)}$ tokens at any given time.⁵⁵5Conditioned on the assumption that $\sigma \le n$, the nodes themselves should hold (all together) less than $n^2$ tokens since a node that holds at least $\sigma$ tokens can perform team formation operations. Regarding the tokens in transit, the algorithm developed in the current paper is designed so that there are less than $\sigma$ tokens in transit over any edge at any given time, so the total number of tokens in transit is $O(n^3)$. The tokens are assumed to be indistinguishable and any number of tokens can be transported over a single message that simply encodes their number.

In the scope of this feature, we distinguish between two types of coin tosses of a node $v\in V$: (1) the finitely many “factory coin tosses” generated by $v$ upon the first activation event of $v$, before any other action of $v$ and hence, could have been generated when $v$ was “manufactured”; (2) all other coin tosses of $v$, generated along the execution. In contrast to the latter, the “factory coin tosses” are considered to be hardwired into $v$’s memory and, in particular, constitute part of $v$’s initial state.

We say that a randomized algorithm satisfies the forgetful feature if it is guaranteed that every node resides in its initial state at any quiescent time (formally defined in Sec. 3.1). Thus, at quiescent times, the nodes may not record any information about their past events and actions. We view the notion of forgetful algorithms as a natural extension of the important notion of memoryless algorithms [57, 59] from deterministic to randomized algorithms and believe that it should be studied further, regardless of the TF problem.

A token $\tau$ injected into node $v\in V$ follows a tour in the communication graph from $v$ to the node $r$ at which $\tau$ is deleted (if at all) as part of a team formation event $F$. Somewhat informally, this tour forms a simple path $\pi$ in the temporal graph that reflects the communication graph along the execution’s time axis (a node $v^{\prime }\in V$ may appear in $\pi$ several times, but at different times). The collection of the paths $\pi$ of all the tokens $\tau$ that participate in $F$ form a temporal tree $T$ rooted at $r$. A TF algorithm satisfies the trace-tree feature if the algorithm maintains a distributed data structure that supports broadcast and echo processes over $T$ (it is the responsibility of “the user” to delete this data structure once it is no longer used). Since the basic description of our TF algorithm, as presented in Sec. 4, does not address this trace-tree feature, we provide the implementation details in [22].

Consider a TF instance and assume that the total number $\mathrm{\ell }$ of tokens injected into the system satisfies $\mathrm{\ell }mod\sigma =k>0$. A TF algorithm satisfies the accumulation feature if it is guaranteed that the $k$ tokens that remain in the system forever are eventually held by the same node.

This is the fundamental one-shot problem of designating a single non-faulty node of a communication network as a leader [49, 7, 52]. We improve upon the previous results for both (1) the implicit version, where each node is required to know whether it is the elected leader; and (2) the explicit version, where, in addition to the above requirement, each non-leader knows which of its (internal) ports leads to the leader. Moreover, our algorithms are fault-tolerant (see Sec. 3.1), while the improved upon prior art [43, 44] assumes fault freedom.

Intuitively, the reduction works as follows: A logarithmic number of nodes are chosen probabilistically to serve as candidates, injecting a token into each one of them. The team size parameter is adjusted so that the number of injected tokens suffices for the formation of exactly one team whp. The node at which the team is formed is elected. In the explicit LE version, on top of the above, the elected leader notifies all other nodes.

We assume that there are at most $n(1/2-ϵ)$ faulty nodes for any constant $ϵ>0$. The run-time of our LE algorithms is $O(\log n)$ whp. Our explicit LE algorithm sends $O(n)$ messages in expectation and whp. This improves upon the time complexity of the best previous algorithms with $O(n)$ messages for asynchronous explicit LE [43, 44]; their time complexity was $({\log }^{2}n)$ even though they assume fault-freedom. Our implicit LE algorithm sends $O(\sqrt{n\log n})$ messages in expectation and $O(\sqrt{n\log n}\cdot \log n)$ messages whp. This is the first algorithm with time complexity $o(n)$ for asynchronous LE (even for fault-free algorithms).

Consider a (long-lived) generalization of the TF problem, where each token comes with a color from a certain color palette and a team should include a pre-specified number of tokens from each color. This problem, called vector team formation (vTF), is formulated as follows: Instead of a scalar team size parameter $\sigma \in {\mathbb{Z}}_{>0}$, the vTF problem is defined over a team size vector $\overrightarrow{\sigma }\in {\mathbb{Z}}_{>0}^m$ whose dimension $m$ corresponds to the size of the color palette; a team now consists of (exactly) $\overrightarrow{\sigma }(i)$ tokens of color $i$ for each $i\in [m]$. As in the TF problem, the safety condition states that tokens can be deleted only as part of a team, whereas the liveness condition states that if the system contains at least $\overrightarrow{\sigma }(i)$ tokens of color $i$ for each $i\in [m]$, then a team must be formed in a finite time. (The aforementioned Dungeons & Dragons example is a special case of vTF.)

To solve vTF, we shall invoke a separate copy of a TF algorithm for each color $i\in [m]$, setting $\sigma =\overrightarrow{\sigma }(i)$, and generate a “super-token” of color $i$ whenever the $i$-th copy forms a team. The super-tokens can then be collected into a vTF team, exploiting the fact that the symmetry is now broken due to the different colors.

The problem of (explicit) agreement with initial failures was defined in the seminal paper of [24] as a contrast to the setting of asynchronous crash failures proved to be impossible. A weaker version of the problem, known as implicit agreement, is defined in [8]. Informally, the latter problem requires that (1) at least one node must decide; (2) the decided value must be the same for all deciding nodes; and (3) the decided value must be the input of some node. This version of the agreement problem was addressed so far only in synchronous networks, considering both fault-free environments [8] and crash faults [40]. As implicit leader election is directly reducible to the aforementioned implicit leader election problem, we obtain an asynchronous implicit leader election algorithm that withstands $n(1/2-ϵ)$ faults in the initial failures model.

This long-lived problem addresses an online gaming platform (see, e.g., [23]) in a “one-versus-one” game mode (two players compete against each other directly like in chess), where players arrive over time and should be matched with opponents. The reduction to TF works as follows: Each player is represented by a single token, which is injected into a relevant node, e.g., a nearby server, and the TF algorithm is invoked with $\sigma =2$. When a team is formed, the trace-tree is used to establish a connection between the servers of the matched players.

In this one-shot problem, the nodes are equipped with unique IDs and an (even size) subset of the (non-faulty) nodes is marked as part of the input. The goal is to form a perfect matching in the subgraph induced by the marked nodes so that each node knows the ID of the node it is matched to. To reduce this problem to TF, intuitively, each marked node generates a token and the TF algorithm is invoked with $\sigma =2$; the trace-tree is employed to allow the matched nodes to exchange IDs.

The one-shot gathering problem requires robots, initially positioned arbitrarily, to meet at a single point within a finite time, where the meeting point is not fixed initially [5, 48, 51, 25, 58]. We propose and solve a new problem called robot team gathering which is a generalization of the gathering problem. Robots are required to form teams of a given (known) size, and each team must meet at a single point within a finite time, where the meeting points are not fixed initially. In the reduction of robot team gathering (in a complete graph) to TF, each robot is represented as a token, and the TF algorithm is used to form teams.⁸⁸8It is not difficult to have the robots (each playing a token) to simulate the algorithms of the nodes, using whiteboards [19, 26] at the nodes.

Consider a network of interconnected devices where the devices count triggers from an external source. In the one-shot distributed trigger counting (DTC) problem, the algorithm is required to raise an alarm when the total number of triggers counted by all the devices reaches a predefined threshold [17, 20, 37]. Intuitively, to solve DTC, each trigger generates a token, and the TF algorithm is invoked after setting the team size parameter to the threshold value.

The application is for the case where a token $\tau$ arrives with some associated information $\mathrm{AS}(\tau )$. It is required that $\mathrm{AS}(\tau )$ be available at the node where the team, that includes $\tau$, is formed at the time of the formation. For example, $\mathrm{AS}(\tau )$ may be a piece of a secret, and $\sigma$ pieces are needed and are enough to recover the secret. We further assume that the information associated with any two tokens that exist in the network simultaneously is different. This means that the size of $\mathrm{AS}(\tau )$ may be large, so only a constant number of such pieces may fit in one message (otherwise, the implementation may be straightforward even if the message size is $O(\log n)$). The reduction to (the standard version of) TF is slightly more technical, see [22].

The execution of $\mathrm{𝙰𝚕𝚐}$ advances through the continuous time axis ${ℝ}_{>0}$ in an event driven fashion so that a node $v\in V$ is activated at time $t>0$ if (and only if) one of the following two activation events occurs at time $t$: (1) a message is delivered to $v$; or (2) one or more tokens are injected into $v$. When activated, the actions of $v$ under $\mathrm{𝙰𝚕𝚐}$ include (I) reading the new incoming message (if any); (II) local computation that may involve (private) random coin tosses; (III) any number of team formation operations; and (IV) sending messages to (a subset of) $v$’s neighbors.⁹⁹9We allow $v$ to send multiple messages to the same neighbor (in practice, those can be piggybacked). It is assumed that actions (I)–(IV) are performed atomically (i.e., they take zero time). We emphasize that the nodes never act unless activation events (1) or (2) occur (in particular, in the scope of the TF problem, there are no “spontaneous wake-ups”).

Assume without loss of generality that the activation events are isolated so that no two of them occur at the same time; the times at which these activation events occur are referred to as activation times. Time $t>0$ is regarded as quiescent if (1) $t$ is not an activation time; (2) there are no messages in transit at time $t$; and (3) the system contains $0$ tokens at time $t$.

For a time $t>0$, let $t-=t-dt$ and $t+=t+dt$ be the times immediately before and immediately after $t$, respectively, where $dt$ is chosen so that the time interval $[t-,t+]$ contains at most one activation event. Given an object $\mathrm{𝚘𝚋𝚓}$, let ${\mathrm{𝚘𝚋𝚓}}^t$ denote the state of $\mathrm{𝚘𝚋𝚓}$ at time $t$, adhering to the convention that ${\mathrm{𝚘𝚋𝚓}}^t={\mathrm{𝚘𝚋𝚓}}^{t-}$ for all $t>0$;¹⁰¹⁰10Objects in this regard include local variables as well as global objects defined for the analysis. in particular, if $t$ is an activation time and the state of $\mathrm{𝚘𝚋𝚓}$ changes at time $t$, then ${\mathrm{𝚘𝚋𝚓}}^t$ is taken to be the state before the change. Notice that our convention implies that instantaneous changes to $\mathrm{𝚘𝚋𝚓}$, that are done as part of the local computation and do not persist beyond time $t$, are not reflected in ${\mathrm{𝚘𝚋𝚓}}^t$.

We adopt a generalization of the initial failures model [18, 24, 60]. Under the initial failures model, the adversary selects a node subset $F\subset V$ at time $0$ (i.e., right before the execution commences) and turns the status of all the nodes in $F$ to faulty, thus preventing them from participating in the execution. In particular, faulty nodes do not send messages and in the context of the TF problem, no tokens are injected into faulty nodes. A message $\mu$ delivered to a faulty node is lost (i.e., it is ignored and does not trigger an activation event). If tokens are transported over a lost message $\mu$, then these tokens are assumed to remain in “limbo” forever, which may prevent the algorithm from satisfying the liveness condition; it is the responsibility of the algorithm designer to avoid such scenarios.

In the (new) generalized version of the initial failures model, considered in the current paper, the adversary may toggle the status of a node $v\in F$ from faulty to non-faulty and vice versa, so that $v$ may participate in the execution in certain time intervals and not participate in others. The decisions of the adversary in this regard are subject to the following constraint: the faulty/non-faulty status of $v$ may be toggled only at quiescent times. For a precise description of the failure model, if $v$ becomes faulty at time $t\ge 0$ and remains faulty until time $t^{\prime }>t$, at which it becomes non-faulty, then the memory image of $v$ at time $t^{\prime }$ is assumed to be identical to that of time $t$. To avoid confusion, we subsequently refer to the nodes in $F$ as fragile (regardless of their faulty/non-faulty status at a specific time of the execution), emphasizing that the non-fragile nodes remain non-faulty throughout the execution.

Notice that due to the asynchronous nature of the system, it may be impossible for a non-faulty node to distinguish its faulty neighbors from the “slow responding” ones. Moreover, the fragile nodes do not know that they are fragile and when a fragile node becomes non-faulty, it runs the same algorithm as the non-fragile nodes. The generalization of the classic initial failures model is different from the crash failures model, where a node may fail at any time. As pointed out in [24], considering initial failures is known to open the gate for asynchronous algorithms that are impossible under crash failures.

With this failure model, the adversary has the following roles: (1) At time $0$, the adversary determines the subset $F\subset V$ of fragile nodes and (without loss of generality) turns their status to faulty. (2) For time $t=0$ and for every activation time $t>0$, at time $t+$, the adversary determines the next activation event (if any) including its type (message delivery or token injection), location, and time $t^{\prime }>t$. (3) For every quiescent time $t>0$ and for every node $v\in F$, the adversary determines (at time $t$) if the faulty/non-faulty status of $v$ is toggled at time $t$ (notice that this is not an activation event). We emphasize that tokens can be injected into node $v$ at time $t$ only if $v$ is non-faulty at time $t$; tokens are never injected into faulty nodes.

The adversary is adaptive, namely, its decisions at time $t$ may be based on the nodes’ actions before time $t$ (however, without knowing the nodes’ future coin tosses). Consequently, the execution of $\mathrm{𝙰𝚕𝚐}$ can be represented as an extensive form game with incomplete information [30], where the adversary is the only strategic player; that is, a rooted tree whose (internal) vertices are partitioned into a set of adversarial moves, in which the adversary makes its decisions, and a set of chance moves, each corresponding to the coin tosses of an activated node in some activation event. Terminology-wise, a mechanism that makes the decision in each adversarial move of the aforementioned extensive form game is referred to as an adversarial policy. Notice that by fixing an adversarial policy, $\mathrm{𝙰𝚕𝚐}$’s execution becomes a random variable, fully determined by the nodes’ coin tosses.

The quality of $\mathrm{𝙰𝚕𝚐}$ is evaluated by means of two performance measures. First and foremost, we wish to bound the number of messages that $\mathrm{𝙰𝚕𝚐}$ sends per token in expectation and whp. Care is needed in this regard since the adaptive nature of the adversary implies that the number of tokens injected into the system may depend, by itself, on the nodes’ coin tosses. Thus, the number of messages per token is, in general, the ratio of two random variables that may exhibit complex dependencies, making it difficult to reason about. To resolve this difficulty, we formulate our main performance measure through the notion of message load, defined as follows.

For $\mathrm{\ell }\in {\mathbb{Z}}_{>0}$, let ${𝒜}_{\mathrm{\ell }}$ be the family of adversarial policies that inject at most $\mathrm{\ell }$ tokens into the system (throughout the execution). We say that $\mathrm{𝙰𝚕𝚐}$’s message load is $M$ in expectation (resp., whp) if $M$ is the smallest real such that for every $\mathrm{\ell }\in {\mathbb{Z}}_{>0}$ and for every adversarial policy in ${𝒜}_{\mathrm{\ell }}$, it is guaranteed that $\mathrm{𝙰𝚕𝚐}$ sends at most $M\cdot \mathrm{\ell }$ messages in expectation (resp., whp).¹¹¹¹11We note that the message load provides a bound on the number of messages sent (per token) in “finite prefixes” of the execution under any adversarial policy, including those that do not belong to ${\bigcup }_{\mathrm{\ell }>0}{𝒜}_{\mathrm{\ell }}$.

We are also interested in the time it takes for $\mathrm{𝙰𝚕𝚐}$ to form a team once sufficiently many tokens are present. To this end, we say that $\mathrm{𝙰𝚕𝚐}$’s reaction time is $R$ if $R$ is the smallest real such that for every time $t>0$, if the system contains at least $\sigma$ tokens at time $t$, then a team is formed by time $t+R$ whp.