Abstract: We consider the problem of a social group of users trying to obtain a "universe" of files, first from a server and then via exchange amongst themselves. We consider the selfish file-exchange paradigm of give-and-take, whereby two users can exchange files only if each has something unique to offer the other. We are interested in maximizing the number of users who can obtain the universe through a schedule of file-exchanges. We first present a practical paradigm of file acquisition. We then present an algorithm which ensures that at least half the users obtain the universe with high probability for $n$ files and $m=O(\log n)$ users when $n\rightarrow\infty$, thereby showing an approximation ratio of 2. Extending these ideas, we show a $1+\epsilon_1$ - approximation algorithm for $m=O(n)$, $\epsilon_1>0$ and a $(1+z)/2 +\epsilon_2$ - approximation algorithm for $m=O(n^z)$, $z>1$, $\epsilon_2>0$. Finally, we show that for any $m=O(e^{o(n)})$, there exists a schedule of file exchanges which ensures that at least half the users obtain the universe.
Introduction
In peer-to-peer (P2P) networking, the "free rider" problem—where users consume resources without contributing—often leads to system inefficiency. To mitigate this, many protocols enforce a Give-and-Take (GT) criterion: two users exchange files only if each possesses at least one unique file that the other lacks. This paper explores how to coordinate these selfish exchanges to maximize the number of users who successfully acquire a complete "universe" of $n$ files.
Problem Formulation
Consider a group of $m$ users seeking a universe $U$ of $n$ files. Initially, users download a subset of files from a central server. Because server bandwidth is costly, users then attempt to complete their collection via local P2P exchanges. The challenge lies in the scheduling: the order of exchanges determines which users can continue to trade. Finding an optimal schedule is computationally complex due to the exponential growth of possible exchange sequences.
The TreeSplit Algorithm
The authors propose the TreeSplit algorithm as a solution for scheduling these exchanges. The algorithm operates by recursively dividing the user base into two equal-sized groups. The fundamental requirement is maintaining a "splitting condition": for any two groups at the same level of the tree, neither group's collective file set should be a subset of the other's.
Exchanges proceed from the leaves (individual users) up to the root (the entire group). At each level, pairs of users or groups trade until they possess the union of their files. This structure ensures that the GT criterion is satisfied at every step of the hierarchy.
Scaling to Large Populations
To handle larger user populations where $m$ is significantly greater than $\log n$, the authors introduce the Partition+TreeSplit approach. Users are first randomly partitioned into smaller "file cover" groups. Each group is designed to collectively possess the entire universe of files. Once these partitions are established, the TreeSplit logic is applied within and across these groups to facilitate the final distribution.
Theoretical Results and Analysis
The paper provides rigorous performance guarantees, expressed as approximation ratios ($\rho$), where $\rho$ is the ratio of the optimal number of satisfied users to the number satisfied by the proposed algorithm:
- Small Groups ($m = O(\log n)$): The TreeSplit algorithm achieves a 2-approximation ratio, guaranteeing that at least half the users obtain the full universe.
- Linear Groups ($m = O(n)$): By allowing users to adjust their initial download probability based on group size, the algorithm achieves a $1 + \epsilon$ approximation, meaning nearly all users can be satisfied.
- Massive Groups ($m = O(e^{o(n)})$): The authors prove that even in exponentially large groups, a schedule exists that satisfies at least half of the participants.
Numerical simulations validate these findings. In tests with 32,768 users and 160 files, the splitting condition held in 99% of cases with an initial download probability of $p=0.10$, allowing the vast majority of the network to reach completion.
Conclusion
This research demonstrates that the constraints of selfish "give-and-take" protocols do not inherently prevent high network utility. Through structured scheduling like TreeSplit, it is possible to ensure that a significant majority of users in a social group can obtain a complete set of resources, even when starting with only a small fraction of the total data.
Summary updated