Notes: 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!