Papers to read (ref: Bitswap)

[jbenet]

We should post papers to read here

[dgrisham]

I'll update this list over time.

SLIC: a selfish link-based incentive mechanism for unstructured peer-to-peer networks

• published 2004, cited by 133
• not quite the same goals as IPFS
• good example of early P2P incentive scheme with no aggregation of trust values
• simulations demonstrating desired properties

Scrivener: Providing Incentives in Cooperative Content Distribution Systems

• published 2005, cited by 77
• very similar goals (and approach, in many ways) to those of IPFS
• 'chain of credit' approach to finding/obtaining blocks from remote nodes
• focuses on mitigating freeriders, assumes sybil attacks handled otherwise
• simulations demonstrating desired properties

P2P Soft Security: On evolutionary dynamics of P2P incentive mechanism

• published 2011, cited by 48
• found by looking at papers referencing PropShare paper
• uses Evolutionary Game Theory (EGT) to evaluate equilibria of 3 P2P strategies:
  1. ALLC: always cooperate, i.e. serve all requests
  2. ALLD: always defect, basically freeriders
  3. R: reciprocate, service all requests to ALLC and R users
• assumes small mutation probability (chance that a user with a particular strategy will suddenly change, modeling user indecision/innovation)
• further assumes probability that user will switch strategies based on who they interact with, e.g. R user interacts with ALLD user, and if ALLD user's utility > R user's utility, there's a higher chance R will switch to ALLD. if this probability tends to be high, we refer to it as the strong selection case. when it's low, we call it the weak selection case
• further assumes small cost to R user for determining the reputation of a user
• also perform analysis with an assumed 'network structure', where users with like-strategies cluster
• results
  • with strong selection and a low mutation probability, strategies tend to oscillate in a rock-paper-scissors pattern (ALLD -> R -> ALLC -> ALLD -> ...)
  • with weak selection and low mutation probability, strategies tend to favor R. as I understand it, this is a good point for maintaining low cost for reputation management in bitswap (e.g. reputation based on firsthand experience only, no aggregation) if the firsthand reputation is (1) a good approximation of global reputation, in general, or (2) reliance on only firsthand experience ends up treating a peer in proportion to the total benefit that peer provides to the network. this is, of course, reliant on the model of this paper fitting Bitswap/IPFS (which it certainly does to a solid extent, but I'm not sure about the R-type user necessarily corresponding directly to the 'ideal'/default bitswap user)
• potential extension: as noted above, R users service all requests for ALLC and R users. but what if R users probabilistically send to a peer based on their history with that peer, similar to the idea of Bitswap? would have to think through this

Multi-Reciprocity Policies Co-Evolution Based Incentive Evaluating Framework for Mobile P2P Systems

• TODO

Analysis and evaluation of incentive mechanisms in P2P networks: a spatial evolutionary game theory perspective

Authors: Guanghai Cui, Mingchu Li, Zhen Wang, Jiankang Ren, Dong Jiao, Jianhua Ma

• Transaction Overlay Network (TON) used to model the fact that peers tend to cluster into subsets (e.g. with peers of similar interest) and are not, in fact, well-mixed
  • Square lattice w/ periodic boundary conditions
  • Each peer has deg 4
  • Neighboring peers have same interest
    • Question: Wouldn't all peers then have same interest?
  • Claim: model easily extended to other topologies, e.g. scale-free
• Reputation based on global peer behavior (shared), not 1-to-1 (private)
  • Reciprocative strategy: reputation has a ceiling -- as soon as peer gives as much as they've received, they cannot increase reputation by giving more (but can decrease by receiving more than they've given). Symmetry seems to make more sense here, and can somewhat incentivize users to be better than 'neutral' (though it also makes sense, I think, to have this decay so that a peer cannot increase reputation indefinitely)
• Learning model based on peers, not global info
  • Also have imperfection/noise to reflect the fact that peers may make irrational choices due to 'imperfect monitoring' and 'learning noises'
  • Thoughts
    • Good because global knowledge unrealistic
    • However, seem to need truthfulness guarantees if learning from peers
      • What if peer has incentive to lie about their utility/strategy?
• Peers are asymmetric
  • Transactions modeled as donor-recipient game (client-server interactions are inherently asymmetric)
  • Rationale: Peer i (client) requesting from peer j (server) does not imply that peer j wants something from peer i at that time
• When a peer changes strategy, their reputation is wiped
  • Rationale
    • User could cooperate to build up reputation, then defect and ride off of the reputation
    • A once-defecting user might switch to cooperation, and the reputation-clearance + better treatment would incentivize them to continue to cooperate
  • Issues
    • Cooperative user might defect for a finite period of time due to 'reasonable' issues (possibly outside of their control), shouldn't lose reputation because of this
    • Defectors could switch to cooperation and have their history of defecting completely wiped as well
    • Alternative
      • Can simply use a strategy to treat a user based on their reputation. This approach would 'decay' allocation to a peer with poor performance, and improve with good performance.
    • If peer earns good reputation, then defect, then they effectively 'spend' the good reputation, which is fair. If peer i sends more to peer j over time, then it's fair that peer i can capitalize on that in a time of need. But peer i has to earn whatever it spends back in the future.
    • If peer earns bad reputation, then they have a lot of work to do in order to improve that reputation, as if they were in debt (hence the whitewashing issue).
• Analysis considers two cases regarding value of peer service:
  1. The value of all peers' service is the same.
  2. Value of peer service follows distribution of some sort (so peer i might provide something worth more than peer j). This value is not dependent on the receiver, it is a constant associated with sender (and remains so for the entire simulation).
• Notes on references
  • 5 (2004) and/or 6 (2003)
    • Discuss 'private' or 'shared' reputation (private being closer to what we want to model in IPFS)
  • 11 (2009)
    • General mathematical framework for evaluating IMs in EGT (specifically in P2P networks)
    • Assumes peers are well-mixed
    • Uses replicator equation, which 'is always used in the case that the population is infinitely large and well-mixed'
  • 19 (1992)
    • Introduces spatial evolutionary game theory
  • 22 (2012)
    • IM for truthful reports in reputation systems
    • Don't need this if peers use 1-to-1 reputation -- no way for peers to lie about how much they've sent you

[dgrisham]

Other papers to look into, found via discussions with @miyazono. These are relatively recent combinations of game theory and mean field theory/renormalization groups, possibly very useful for a large-scale Bitswap analysis.

• Mean Field Games and Applications: Overview/examples of using mean field models to analyze large systems of players in a game theoretical situation. There are quite a few examples, with part of their intent being to give an idea of applications where this kind of model makes sense/how to approach such problems.
• Game Theory and Topological Phase Transition: Still need to look this one over, I'll update this comment once I do.

[daviddias]

@dgrisham just updated the README for this research repo, mind adding all of these papers there? https://github.com/ipfs/research-bitswap#papers thanks!