Rarest-First with Probabilistic-Mode-Suppression (RFwPMS)

A series of recent works have appeared of which the relevant papers are [6, 4, 5, 1, 9, 10, 11, 12, 13, 7, 8].

• •

  Zhu and Hajek [6], in a follow-up to [5], showed that if, after completing their file-download, each peer remains in the system long enough to upload one additional piece, then the network is stable under any positive seed uploading capacity and any peer arrival rate. This demands persistence of peers, which might not hold, especially with wireless users who are sensitive to their energy and bandwidth usages. Thus, recent works have also covered piece-selection policies that ensure stability when peers are strictly non-persistent.

• •

  Massoulié and Vojnović [4] considered a BitTorrent-like stochastic system where before entering the system, users obtain one piece (referred to as coupon in [4]) from a central bootstrap server. Under this assumption, they showed that the performance of the network does not depend critically on either persistence of users or on load balancing piece-selection policies like RF.

• •

  Norros, Reittu and Eirola [1] proposed the Enforced Friedman algorithm in which a peer makes three contacts simultaneously (with replacement) and if there are ‘minority pieces’ (pieces possessed by exactly one of the three peers), then the peer downloads one of them uniformly at random. If there are no minority pieces, then the peer waits for the next triple contact. The stability of the protocol was shown for a two-chunk file-sharing system whereas for the case of a multi-chunk system, it was left as a conjecture, with numerical simulations providing good evidence of stability. In a follow-up work, Oguz, Anantharam and Norros [9] proved the stability of the Enforcement Friedman protocol for multi-chunk systems and also proposed a provably stable improvement under the name of Common Chunk protocol. In this protocol, only new peers who arrive with no pieces follow the rules in [1], and the peers who lack only one piece contact three peers and are allowed to download the last piece only if every piece they have is present with at least two of the three contacted peers.

• •

  Bilgen and Wagner [10, 19] proposed the Group Suppression Protocol in which peers who share the same piece profile are defined as a group and the group with the largest population is defined as the largest club. The protocol states that a peer belonging to the largest club uploads only to those peers who hold greater number of pieces than it does, and refuses the upload to all other peers if it contacts them. The protocol was proved to be stable for a two-chunk file-sharing system and its stability for multi-chunk systems was left as a conjecture.

• •

  Reddyvari, Parag and Shakkottai [11] took a chunk-level viewpoint and proposed the Mode-Suppression (MS) protocol. Here, the transfer of pieces in the mode (present with the most number of peers) is prohibited, except when all pieces are in the mode, and a random-novel piece not in the mode (if any) is sent. In a follow-up [12, 13], Reddyvari, Parag and Shakkottai prove the stability and scalability of Threshold Mode-Suppression (TMS) wherein pieces in the mode are prohibited from transfer when the largest-mismatch (difference between chunk-counts of the most-abundant and the rarest chunks, see 3) crosses a certain fixed threshold. This line of work showed stability and scalability for all arrival rates in the single-swarm setting.

• •

  Previous works have also considered bundling different swarms together in the same network and then allowing content-sharing across them. This was proposed by Zhou, Ioannidis and Massoulié [7] with the claim that such “universal swarms” can increase the stability region of a BitTorrent network. Then Zhu, Ioannidis, Hegde and Massoulié [8] formally characterized the stability region of such networks when a work-conserving piece-selection policy is used. The stability region is indeed larger than in the single-swarm setting, however, yet again, it doesn’t hold for all arrival rate configurations.

The contributions of this paper are listed below:

1. a)

   Developing a tractable model (that extends the stochastic model from [5] and [6]) for the analysis of file-sharing P2P networks that employ tit-for-tat and optimistic-unchoke mechanisms;

2. b)

   Demonstrating that instability occurs when a hard tit-for-tat rule is used without optimistic-unchoking. Here, instability occurs due to a first-piece syndrome (FPS) where newly arriving peers have to rely solely on the seed to get their first piece (Proposition 1);

3. c)

   Showing that soft tit-for-tat or optimistic-unchoking mechanisms cannot ward off the last-piece-syndrome in the presence of a work-conserving piece-selection policy (Proposition 2);

4. d)

   In a general multi-swarm setting, proposing the swarm-based RFwPMS piece-selection policy and proving its stability using a novel Lyapunov function (Theorem 1).

5. e)

   Demonstrating the scalability of swarm-based RFwPMS in the single-swarm case, i.e., the expected steady-state sojourn time is upper-bounded by a constant which is independent of the arrival-rate of the incoming peers.⁶⁶6Establishing the scalability in the general multi-swarm case is left as an open problem. (Theorem 4).

6. f)

   Showing improved performance of swarm-based RFwPMS in steady-state and flash-crowds via numerical simulations.

A preliminary version of this work was presented in [15] with a partial theoretical analysis and a sub-case of the general stochastic model studied here. The current work adds to the contributions of [15] – items a) through f) above – and provides the complete details associated with the stability analysis of swarm-based RFwPMS.

Since the single-swarm model is a special case of the multi-swarm model, henceforth we only consider the multi-swarm model, except when we discuss our scalability results. The remainder of the paper is organized as follows. In Section II, we introduce the multi-swarm model which is built upon the model in [8]. Section III presents the main stability theorem along with the preliminary setup needed for the detailed proof (the detailed proof is provided in Appendix E). Section IV discusses the working of RFwPMS as well as a few types of swarm behaviors that can be relevant in specific P2P environments and follow naturally as a result of the general nature of our assumption on inter-swarm behaviors. Section VI presents few important snapshots of numerical results on stability, scalability and performance of RFwPMS. Finally, in Section VII, we give concluding remarks and few future-work directions.

To aid the reading experience, we encourage the reader to refer to the relevant notation and definitions detailed in Appendix G.

A master-file, denoted by $\mathcal{F}$, is chopped into at least two equally-sized pieces, i.e., $\mathcal{F}=[K]$⁷⁷7For $c,d\in\mathbb{Z}=\{\dotsc,-1,0,1,\dotsc\}$ and $c<d$, we use the standard notation $[c,d]:=\{c+1,\dotsc,d\}$ and $[d]$ for $[0,d]$ when $d\in\mathbb{N}=\{1,2,\dotsc\}$. where $K\geq 2$. There is a distinguished peer, the seed, which holds this master-file $\mathcal{F}$ and stays in the network indefinitely. The existence of the seed for indefinite period of time ensures that every piece is available in the network at all times, thus allowing us to study the long-term behavior of the network. We define file-$W$ as any non-empty subset of the master-file, thus, $W\neq\emptyset$ and $W\subseteq\mathcal{F}$. The number of pieces in file-$W$ is denoted by $K_{W}$, i.e., $K_{W}=|W|$. With this definition of file, swarm-$W$ is defined as the set of peers who are primarily interested in downloading (pieces of) file-$W$. We note that peers entering the network can be interested in any file, i.e., the files need not be disjoint subsets of $\mathcal{F}$. Besides their primary interest in file-$W$, swarm-$W$ peers may also have a secondary preference for some other pieces of the master-file. Thus, the set of pieces that a swarm-$W$ peer can download during its stay in the network is given by $\mathcal{F}_{W}$ where $W\subseteq\mathcal{F}_{W}\subseteq\mathcal{F}$. It is assumed that peers enter the network according to independent Poisson processes, i.e., a swarm-$W$ peer enters the network according to a Poisson process of rate $\lambda_{W}>0$, independent of other swarms. Let $\mathcal{W}$ denote the set of all swarms that join the network and let $\bm{\lambda}=(\lambda_{W}:W\in\mathcal{W})$ denote the vector of their arrival-rates. We now list three important assumptions of the model.

1. a)

   Empty Cache upon Arrival: Each peer maintains a cache to store the pieces it downloads. The cache is empty upon arrival and has a capacity of $|\mathcal{F}_{W}|$ pieces. The part of the cache that is devoted for the pieces of secondary interest is called the excess-cache (where pieces from the set $\mathcal{F}_{W}\setminus W$ are stored). In the context of [4], empty cache assumption aligns with the case when the central bootstrap server is bottlenecked, for example, in the case of a high peer arrival-rate or during a flash-crowd⁸⁸8A situation in which the network suddenly encounters a very large number of empty peers; this is commonly seen with torrents of popular files..

2. b)

   Ally Swarms: While peers interested in the same file (i.e., belonging to the same swarm) exchange pieces with each other, they may or may not prefer to collaborate with peers who are interested in other files (i.e. peers belonging to a different swarm). Thus, each swarm has an associated set of ally-swarms. Formally, the ally-set of swarm-$W$, denoted by $\mathcal{W}_{W}$, is a non-empty subset of $\mathcal{W}$ that consists of swarm-$W$ as well as any other swarms to which its peers can upload pieces ($W\in\mathcal{W}_{W}\subseteq\mathcal{W}$); and

3. c)

   Strictly Non-persistent Peers: Once a peer finishes downloading their pieces of primary interest, they leave the network immediately.

The notation used in this paper is a combination of related notations in [8] and [11]. We classify peers into types according to the swarm they belong to, and the set of pieces in their cache. Hence, a peer in swarm $W$ holding $S\subseteq\mathcal{F}_{W}$ is said to be of type $(W,S)$. We denote the number of $(W,S)$-type peers at time $t\geq 0$ by $x_{W}^{(S)}(t)\in\mathbb{Z}_{+}\coloneqq\{0,1,\dots\}$. Then the state of the network at time $t$ is given by the vector

Note that as a result of aforementioned assumptions, the cache-profile $S$ of a swarm-$W$ peer always satisfies the conditions $S\subseteq\mathcal{F}_{W}$ and $W\setminus S\neq\emptyset$, with the latter condition capturing strictly non-persistent peers. For the sake of brevity, from hereon, we will omit writing these two conditions. Also, since the fixed seed is always present in the network, we do not include it in $\mathbf{x}(t)$. The population of swarm-$W$, i.e., the number of swarm-$W$ peers at time $t$ is given by

Similarly, the total number of peers at time $t$ is given by

From hereon, for brevity, we will write $\mathbf{x}(t)$ as $\mathbf{x}$ since the dependence on time $t$ will be clear from the context.

Consistent with the stochastic models of [1, 4, 5, 6, 10, 11, 12, 8, 7, 9], we assume that the network employs random peer-contacts. Specifically, it is assumed that each peer has a fixed number of contact-links, denoted by $L\geq 1$. In normal peers, the first $\left(L-\mathbbm{1}{\{Y_{opt}=1\}}\right)$ of these links are reserved for tit-for-tat based piece exchanges whereas the $L^{th}$ link is used for optimistic-unchoking if and only if $Y_{opt}=1$; otherwise it is also used for tit-for-tat based piece exchanges. Here, $Y_{opt}$ is a binary parameter that is set to 1 if optimistic-unchoking is desired as part of the peer-contact policy. In contrast to normal peers, all the $L$ links of the fixed seed are used for optimistic-unchokes.

For normal peers, we assume that each tit-for-tat link is activated according to an independent Poisson process of rate $\mu>0$ and the optimistic-unchoke link is activated according to another independent Poisson process of rate $\hat{\mu}>0$. Upon activation of the link, the peer contacts, uniformly at random, some other (normal) peer from the network.⁹⁹9The motivation behind introducing a separate rate for the optimistic-unchoke link comes from how BitTorrent operates. In practice, by default, the number of links $L$ is 5, and which peer is optimistically-unchoked is rotated roughly every third tit-for-tat period (see [2]). By introducing $\mu$ and $\hat{\mu}$, this can be captured by our model by setting $\hat{\mu}=\frac{\mu}{3}$. For more details, see [2]. For the fixed seed, each of its (optimistic-unchoke) links is activated according to a Poisson process of rate $U>0$. We assume that the transfer of piece/s occurs instantaneously with the contact (in reality, this will take more time than initiating a contact).

To define the tit-for-tat and optimistic-unchoking mechanisms, let us imagine a contact in which a peer, say peer-(1), which is of type $(W_{1},S_{1})$, has contacted another peer, say peer-(2), which is of type $(W_{2},S_{2})$. The interaction between the two peers depends on the type of contact that peer-(1) has made with peer-(2). Thus, there are two cases.

1. a)

   Tit-for-Tat Contact: In this case, both peers first check the swarm-identity of each other following which they reveal their cache-profiles (based on how they view each other’s swarm). Specifically, for each $k=1,2$, the following events happen sequentially.

   1. i)

      Peer-$(k)$ shares its swarm-identity $W_{k}$ with peer-($-k$).¹⁰¹⁰10Here, $-k$ denotes the element in $\{1,2\}\setminus\{k\}$.

   2. ii)

      If $W_{-k}\notin\mathcal{W}_{W_{k}}$, Peer-$(k)$ reveals an empty cache-profile, $\widehat{S}_{k}=\emptyset$¹¹¹¹11This ensures that no piece is transferred to a non-ally peer., otherwise it shows its true cache-profile, $\widehat{S}_{k}=S_{k}$. We call $\widehat{S}_{k}(\cdot)$ the revealed cache-profile of peer-$(k)$.

   3. iii)

      Peer-$(k)$ checks if the contact is potentially useful, i.e., if $(\widehat{S}_{-k}\cap W_{k})\setminus S_{k}$ is non-empty. ¹²¹²12Checking $(\widehat{S}_{-k}\cap W_{k})\setminus S_{k}$ instead of $(\widehat{S}_{-k}\cap\mathcal{F}_{W_{k}})\setminus S_{k}$ matches with our assumption that extra pieces (in $\mathcal{F}_{W}\setminus W$) are given secondary preference. If $(\widehat{S}_{-k}\cap W_{k})\setminus S_{k}$ is non-empty, peer-$(k)$ commits to transfer some piece to peer-$(-k)$ from $\widehat{S}_{k}$. If $(\widehat{S}_{-k}\cap W_{k})\setminus S_{k}$ is empty, the network forces peer-$(k)$ to conduct a Bernoulli($p$) trial, only upon the success of which, it must commit to transfer some piece to peer-$(-k)$ from $\widehat{S}_{k}$. Once peer-$(k)$ has committed to transfer a piece to peer-$(-k)$ from $\widehat{S}_{k}$, we say that “peer-$(k)$ has push-contacted peer-$(-k)$ under revealed cache-profile $\widehat{S}_{k}$” or equivalently “peer-$(-k)$ has pull-contacted peer-$(k)$ with revealed cache-profile $\widehat{S}_{k}$”. Here, importantly, we note that the probability of this push-contact is at least $p$.

2. b)

   Optimistic Unchoke: In this case, peer-$(1)$ checks the swarm-identity $W_{2}$ and then push-contacts peer-$(2)$ with revealed cache-profile $\widehat{S}_{1}(W_{2})$.

From a) and b), it is clear that no piece is transferred from peer-$(k)$ to peer-$(-k)$ if $W_{-k}\notin\mathcal{W}_{W_{k}}$ ($k=1,2$). Hence, we need not consider push-contacts from a peer to its non-ally peer. Once a push-contact has been made, which exact piece is chosen for transfer and whether the transfer is successful or not, is determined by the network’s piece-selection policy. This is described next.

Suppose that at time $t\geq 0$, a $(V,T)$-peer has push-contacted its ally-peer, say a $(W,S)$-peer ($W\in\mathcal{W}_{V}$), with revealed cache-profile $\widehat{T}$. To describe Swarm-based RFwPMS, some definitions (a’la [11, 12, 13]) are needed.

Unless otherwise noted, we will refer to a rare-piece by $r$, a non-rare piece by $n$, and importantly many times, the rarest piece (one with the lowest chunk-count) by $\underline{r}$. We now list the rules of swarm-based RFwPMS for a possible piece transfer from the $(V,T)$-peer to (its ally) $(W,S)$-peer, when $(V,T)$-peer reveals cache-profile $\widehat{T}$:

1. a)

   Download of a Rare Piece: If a rare-piece is available for transfer, i.e., $\left(\widehat{T}\cap R_{W}(\mathbf{x})\right)\setminus S\neq\emptyset$, then the $(V,T)$-peer uploads the rarest piece it can offer, i.e., a piece chosen uniformly at random from the set

   $\displaystyle\underline{R}_{(\widehat{T},W,S)}(\mathbf{x})\coloneqq\operatorname*{arg\,min}\limits_{j\in\left(\widehat{T}\cap R_{W}(\mathbf{x})\right)\setminus S}c^{(j)}_{W}(\mathbf{x}).$

   (14)

2. b)

   Download of a Non-rare Piece: In the case that no rare piece is available for transfer but a non-rare piece is, i.e., $\left(\widehat{T}\cap R_{W}(\mathbf{x})\right)\setminus S=\emptyset$ and $(\widehat{T}\cap W)\setminus S\neq\emptyset$, then the $(V,T)$-peer chooses some non-rare piece $n\in(\widehat{T}\cap W)\setminus S$ uniformly at random, and uploads it only if the result of a Bernoulli$\left(\zeta_{W}^{(n)}(\mathbf{x})\right)$ trial is a success. We refer to $\zeta_{W}^{(n)}(\mathbf{x})$ as the non-rares’ sharing factor and it is defined as follows.

   $\displaystyle\zeta_{W}^{(n)}(\mathbf{x})\coloneqq\begin{cases}\exp\left(-\frac{\left(\overline{m}_{W}(\mathbf{x})+\left(d^{(n)}_{W}(\mathbf{x})\right)^{\alpha_{W}}\right)}{\beta_{W}K_{W}}\right)&\text{if $\beta_{W}>0$},\\ 0&\text{if $\beta_{W}=0$}.\end{cases}$

   (15)

   Here, $\beta_{W}\geq 0,\alpha_{W}\in(0,1]$ are tuning parameters. (As an aside, note that complete mode-suppression is covered as we allow $\beta_{W}=0$).

   Intuition: Let us develop some intuition about our specific choice of $\zeta_{W}^{(n)}(\mathbf{x})$. As indicated earlier in Section I, the mode-suppression (MS) protocol [12] strictly forbids the replication of non-rare pieces. This does a good job of maintaining a uniform chunk-distribution throughout the network’s evolution. However, there is an accompanying undesirable effect – no piece is transferred in all those push-contacts wherein only the non-rare pieces are available for transfer. As shown in Section VI, this can incur a high penalty on the file-delivery time during a flash-crowd.¹³¹³13A situation in which the network suddenly encounters a very large number of empty peers; this is commonly seen with torrents of popular files. Besides flash-crowds, even under normal operating conditions, completely suppressing non-rare pieces is unnecessary and, as indicated in [12], a trade-off exists between their suppression and sharing. Swarm-based RFwPMS allows for tuning this trade-off via $\zeta_{W}^{(n)}$.

   Even though different swarms are coupled together in the same system, one can optimistically expect that if each swarm tries to uniformly maintain its own chunk-distribution, the stochastic system should hopefully converge to some form of equilibrium (after possibly some temporary transient behavior due to the effects of other swarms). Keeping this in mind, the first term of $\zeta_{W}^{(n)}$, i.e.,

   $$\exp\left(-\frac{\overline{m}_{W}(\mathbf{x})}{\beta_{W}K_{W}}\right),$$

   is intended to increase the probabilistic-suppression of non-rare pieces as the total-mismatch becomes larger. (We use $\overline{m}_{W}$ as a simple proxy for $M_{W}$).

   Ideally, we would have liked $\zeta_{W}^{(n)}$ to consist of the first term only. But showing stability of our multi-swarm model in that case is hard. The key technical difficulty behind this is the form of the Lyapunov function that we have engineered (see (26), (27)), and our analysis of the unit-transition drift (where we are effectively trying to decouple the inter-swarm effects). There, if we consider states with large $\overline{m}_{W}$ and a large complementary chunk-count $d^{(n)}_{W}$, then the suppression through $\exp\left(-\frac{\overline{m}_{W}(\mathbf{x})}{\beta_{W}K_{W}}\right)$ turns out to be insufficient to satisfy the unit-transition drift conditions. (The term $\exp\left(-\frac{\overline{m}_{W}(\mathbf{x})}{\beta_{W}K_{W}}\right)$ cannot shrink a polynomial term in $d^{(n)}_{W}$). All is not lost however, as we circumvent this technical issue, by introducing the second suppression term

   $$\exp\left(-\frac{\left(d^{(n)}_{W}(\mathbf{x})\right)^{\alpha_{W}}}{\beta_{W}K_{W}}\right),$$

   where by choosing $\alpha_{W}\in(0,1]$ sufficiently small, $\zeta_{W}^{n}(\mathbf{x})$ effectively becomes a function of the ratio of swarm-$W$’s total-mismatch to its file-size $K_{W}$. The higher this ratio, the lesser the likelihood that the (non-rare) piece $n$ gets replicated. The choice of the ratio instead of just the total-mismatch matches the intuition that a file with large number of pieces should allow more sharing of non-rare pieces as opposed to a file with smaller number of pieces.

3. c)

   Download of an Extra Piece: If, from rules (b) and (c), no piece of file-$W$ could be uploaded to the $(W,S)$-peer, then the $(V,T)$-peer uploads an extra piece chosen uniformly at random from the set $(\widehat{T}\cap\mathcal{F}_{W})\setminus(S\cup W)$.

With the above three rules, the transferable-set $A(\mathbf{x},\widehat{T},W,S)$ for swarm-based RFwPMS can be computed according to Algorithm 1. By transferable set, we mean the set of pieces chosen for transfer by the piece-selection policy – in our case, the transferable set will either be empty or a singleton set.

In order to extend our rules to the seed, we assume that the seed is a $(\dagger,\mathcal{F})$-type peer¹⁴¹⁴14For example, $\dagger$ can be $\mathcal{F}\cup\{K+1\}$. with the ally-set $\mathcal{W}_{\dagger}=\mathcal{W}$. Thus, the set of rare pieces when the seed push-contacts a normal peer is given by

Remark: Note that when there is no rare piece at offer, a non-rare piece $n\in(T\cap W)\setminus S$ is transferred only probabilistically, so swarm-based RFwPMS is not a work-conserving scheme.

Remark: With rules a), b) and c), we note that each swarm maintains its own chunk-table and also prioritizes its primary pieces over other pieces of the master-file. For these two reasons, we call our policy, “swarm-based” RFwPMS.

For the sake of notational simplicity, from hereon, we will write function $f(\cdot)$ as $f$ when the dependence on the argument is clear. At any given current state $\mathbf{x}$, the next state of the network depends solely on $\mathbf{x}$ because the piece-selection policy solely depends on $\mathbf{x}$ and the new arrivals (empty peers) are determined by an independent Poisson process. Hence, the evolution of the network described by the process $\{\mathbf{x}(t):t\geq 0\}$ is a continuous-time, time-homogeneous, and irreducible (easily shown) Markov chain with state space,

Given a state $\mathbf{x}$, there are different events that can lead to state-transitions, namely, the arrival of a new empty peer, the download of a single-piece or a (two-sided) piece-exchange (download of two pieces simultaneously as a result of some tit-for-tat contact). Here, we do not list the transition rates of (two-sided) piece-exchanges: later in Section III, we will see that with our choice of Lyapunov function, such transitions can be viewed as two separate single-piece-download events. The result of each event is given below.

1. a)

   Arrival of an Empty-peer: Recall that a swarm-$W$ peer with an empty cache enters the network according to a Poisson process of rate $\lambda_{W}$. This results in a unit increase in the number of swarm-$W$ peers with no pieces. Let us denote this transition by $\{(\emptyset,+)_{W}\}$ and its corresponding rate by $q_{W}^{(\emptyset+)}$. Then

   $\displaystyle q_{W}^{(\emptyset+)}=\lambda_{W}.$

   (17)

2. b)

   Download of Piece of Primary Interest: Consider the event that a $(W,S)$-peer missing piece $i\in W$ downloads piece $i$. The necessary condition for this event is that $(W,S)$-peer gets push-contacted by a $(V,T)$-peer such that $W\in\mathcal{W}_{V}$ and $i\in T$. There are three distinct ways in which this can happen.

   1. i)

      The $(W,S)$-peer gets push-contacted by the $(V,T)$ peer as a result of a tit-for-tat contact initiated by the $(V,T)$-peer. By the superposition and thinning properties of Poisson processes, the rate at which an ally peer of swarm $W$ with piece $i$ makes a tit-for-tat contact with a $(W,S)$-peer is

      $\displaystyle\left(\mu\sum_{\begin{subarray}{c}V:W\in\mathcal{W}_{V},\\ T:i\in T\end{subarray}}x_{V}^{(T)}\right)\cdot(L-\mathbbm{1}{\{Y_{opt}=1\}})\frac{x_{W}^{(S)}}{|\mathbf{x}|}\frac{|\mathbf{x}|}{|\mathbf{x}|-1}.$

   2. ii)

      The $(W,S)$-peer gets push-contacted by the $(V,T)$-peer as a result of an optimistic-unchoke (initiated by the $(V,T)$-peer). The rate at which a $(W,S)$-peer gets contacted in an optimistic-unchoke by an ally-peer having piece $i$ is given by

      	$\displaystyle UL\cdot\frac{x_{W}^{(S)}}{|\mathbf{x}|}+\left(\mathbbm{1}{\{Y_{opt}=1\}}\hat{\mu}\sum_{\begin{subarray}{c}V:W\in\mathcal{W}_{V},\\ T:i\in T\end{subarray}}x_{V}^{(T)}\right)$
      	$\displaystyle\hskip 120.0pt\times\frac{x_{W}^{(S)}}{|\mathbf{x}|}\frac{|\mathbf{x}|}{|\mathbf{x}|-1}.$

   3. iii)

      The $(W,S)$-peer gets push-contacted by the $(V,T)$-peer as a result of a tit-for-tat contact initiated by the $(W,S)$-peer. The rate at which a $(W,S)$-peer makes a tit-for-tat contact with an ally-peer that has piece $i$ is

      $\displaystyle\left(\mu x_{W}^{(S)}\right)\cdot(L-\mathbbm{1}{\{Y_{opt}=1\}})\frac{\sum_{\begin{subarray}{c}V:W\in\mathcal{W}_{V},\\ T:i\in T\end{subarray}}x_{V}^{(T)}}{|\mathbf{x}|}\frac{|\mathbf{x}|}{|\mathbf{x}|-1}.$

   Let us denote by $\Gamma_{W}^{(i)}=\Gamma_{W}^{(i)}(\mathbf{x})$ the aggregate rate at which an ally peer of swarm-$W$ with piece $i$ push-contacts some other peer in the network. The exact form of $\Gamma_{W}^{(i)}$ is complicated, however, from i), ii), iii) and our descriptions of tit-for-tat and optimistic-unchoke, we can bound it both from above and below. Let

   	$\displaystyle\underline{\Gamma}_{W}^{(i)}(\mathbf{x})$	$\displaystyle\coloneqq LU+\Delta_{p}\xi_{1}\left(c^{(i)}_{W}+d^{(i)}_{W}\right)$
   		$\displaystyle\geq LU+\Delta_{p}c^{(i)}_{W}.$		(18)

   and

   	$\displaystyle\overline{\Gamma}_{W}^{(i)}(\mathbf{x})$	$\displaystyle\coloneqq LU+\Delta_{1}\xi_{1}\left(c^{(i)}_{W}+d^{(i)}_{W}\right)$
   		$\displaystyle\leq LU+2\Delta_{1}\left(c^{(i)}_{W}+d^{(i)}_{W}\right),$		(19)

   where, for brevity, we have introduced $\xi_{1}\coloneqq\xi_{1}(\mathbf{x})=\frac{|\mathbf{x}|}{|\mathbf{x}|-1}\in(1,2]$ (for all $|\mathbf{x}|\geq 2$), and $\Delta_{t}\coloneqq 2(L-\mathbbm{1}{\{Y_{opt}=1\}})\mu t+\mathbbm{1}{\{Y_{opt}=1\}}\hat{\mu}$. It is clear that

   $\displaystyle\underline{\Gamma}^{(i)}_{W}\leq\Gamma^{(i)}_{W}\leq\overline{\Gamma}^{(i)}_{W}.$

   (20)

   and

   	$\displaystyle\frac{\overline{\Gamma}_{W}^{(i)}}{\underline{\Gamma}_{W}^{(i)}}$	$\displaystyle=\frac{LU+\Delta_{1}\xi_{1}\left(c^{(i)}_{W}+d^{(i)}_{W}\right)}{LU+\Delta_{p}\xi_{1}\left(c^{(i)}_{W}+d^{(i)}_{W}\right)}$
   		$\displaystyle\leq\xi_{2}\coloneqq\begin{cases}1+\frac{2(L-1)\mu+\hat{\mu}}{2(L-1)\mu p+\hat{\mu}}&\text{if $Y_{opt}=1$,}\\ 1+\frac{1}{p}&\text{if $Y_{opt}=0$.}\\ \end{cases}$		(21)

   Here, $\xi_{2}=\xi_{2}(Y_{opt},L,p,\mu,\hat{\mu})$ is a constant that depends on the model parameters.

   After the $(W,S)$-peer has downloaded piece $i$, depending on $S$, it will either remain in the network or leave it immediately. Therefore, we have two cases:

   1. i)

      if $W\setminus S\supsetneq\{i\}$, the peer stays in the system. Let us denote this transition by $\{(S,i+)_{W}\}$ and the corresponding rate by $q_{W}^{(S,i+)}$. Based on the description of swarm-based RFwPMS, $q_{W}^{(S,i+)}$ depends on whether $i\in R_{W}$ or $i\in R^{c}_{W}$. If $i=r$ is some rare piece in $R_{W}$, then we have

      		$\displaystyle\frac{x_{W}^{(S)}}{|\mathbf{x}|}\underline{\Gamma}_{W}^{(r)}\xi_{2}\geq\frac{x_{W}^{(S)}}{|\mathbf{x}|}\overline{\Gamma}_{W}^{(r)}\geq q_{W}^{(S,r+)}\geq\dots$
      		$\displaystyle\hskip 10.0pt\geq\frac{x_{W}^{(S)}}{|\mathbf{x}|}\left[\frac{LU\mathbbm{1}{\{r\in\underline{R}_{(\mathcal{F},W,S)}\}}}{|\underline{R}_{(\mathcal{F},W,S)}|}\right.$
      		$\displaystyle\hskip 10.0pt\left.+\Delta_{p}\xi_{1}\sum\limits_{\begin{subarray}{c}V:W\in\mathcal{W}_{V},\\ T:r\in T\end{subarray}}\frac{\mathbbm{1}{\{r\in\underline{R}_{(T,W,S)}\}}}{|\underline{R}_{(T,W,S)}|}x_{V}^{(T)}\right],$		(22)

      where the two indicator terms ensure that piece $r$ is transferred only if it is the rarest of all the available rare pieces. Importantly, when the chunk-distribution in swarm-$W$ is uniform i.e., $\overline{c}_{W}=\underline{c}_{W}$, by definition, $R_{W}=W$ and the above expression assumes a more tractable form. Therefore, for each swarm-$W$, we partition the state space into two regions, namely $\mathcal{S}^{1}_{W}$ and $\mathcal{S}^{2}_{W}$, where $\mathcal{S}^{1}_{W}=\{\mathbf{x}\in\mathcal{S}:R_{W}(\mathbf{x})\subsetneq W\}$, and $\mathcal{S}^{2}_{W}=\{\mathbf{x}\in\mathcal{S}:R_{W}(\mathbf{x})=W\}$.¹⁵¹⁵15When $\mathbf{x}\in\mathcal{S}^{2}_{W}$, both the indicator terms in ( ‣ b)) evaluate to 1. If $i=n$ is some non-rare piece in $R^{c}_{W}$, then

      $\displaystyle\underline{q}_{W}^{(S,n+)}\leq q_{W}^{(S,n+)}\leq\frac{x_{W}^{(S)}}{|\mathbf{x}|}\overline{\Gamma}_{W}^{(n)}\zeta_{W}^{(n)}\leq\frac{x_{W}^{(S)}}{|\mathbf{x}|}\underline{\Gamma}_{W}^{(n)}\xi_{2}\zeta_{W}^{(n)},$

      (23)

      where

      	$\displaystyle\underline{q}_{W}^{(S,n+)}$	$\displaystyle\coloneqq\frac{x_{W}^{(S)}}{|\mathbf{x}|}\left[\frac{LU\mathbbm{1}{\{R_{W}\setminus S=\emptyset\}}}{|W\setminus S|}\right.$
      		$\displaystyle\left.+\Delta_{p}\xi_{1}\sum_{\begin{subarray}{c}V:W\in\mathcal{W}_{V},\\ T:n\in T\end{subarray}}\frac{x_{V}^{(T)}\mathbbm{1}{[(T\cap R_{W})\setminus S=\emptyset]}}{|(T\cap W)\setminus S|}\right]\zeta_{W}^{(n)}.$		(24)

   2. ii)

      If $W\setminus S=\{i\}$, the only piece of file-$W$ that is missing with the $(W,S)$-peer is piece $i$. Consequently, for both $\mathbf{x}\in\mathcal{S}^{1}_{W}$ and $\mathbf{x}\in\mathcal{S}^{2}_{W}$, piece $i$ is the rarest piece transferable to the $(W,S)$-peer, which leaves the network immediately upon downloading it. Let us denote this transition by $\{(S,i-)_{W}\}$ and its corresponding rate by $q_{W}^{(S,i-)}$. Then,

      $\displaystyle\frac{|\mathbf{x}|_{W}}{|\mathbf{x}|}\frac{x_{W}^{(S)}}{|\mathbf{x}|_{W}}\underline{\Gamma}_{W}^{(i)}a_{W}^{(i)}\leq q_{W}^{(S,i-)}\leq\frac{|\mathbf{x}|_{W}}{|\mathbf{x}|}\frac{x_{W}^{(S)}}{|\mathbf{x}|_{W}}\underline{\Gamma}_{W}^{(i)}\xi_{2}a_{W}^{(i)},$

      (25)

      where, for brevity, we introduced $a_{W}^{(i)}=a_{W}^{(i)}(\mathbf{x})\coloneqq\zeta_{W}^{(i)}\mathbbm{1}{\{i\in R^{c}_{W}\}}+\mathbbm{1}{\{i\in R_{W}\}}$.

3. c)

   Download of Extra Piece: Recall that extra pieces are preferred only when no pieces from the file of primary interest are transferable. We shall see that the drift analysis of our Lyapunov function does not depend on the download of extra pieces. Consequently, we skip listing the associated rates.

While it is clear that a tit-for-tat mechanism helps combat the last-piece-syndrome, the issue of quantifying its efficacy via a suitable model was left as an open problem in [5]. Our stochastic model described above is partly motivated by this question. In this subsection, we show that introducing tit-for-tat does not prevent instability if a work-conserving piece-selection policy (like RF and RN) is used.

Figure2 shows the first-piece-syndrome manifested in a single-swarm network using a hard tit-for-tat mechanism without optimistic-unchoking.

Propositions 1 and 2 motivate the design of a piece-selection policy that is provably stable in file-sharing networks that employ the “Soft Tit-for-Tat” and the “Hard Tit-for-Tat with Optimistic-Unchoking” mechanisms.