Incentivos en
Redes P2P
Bibliografía
M. Feldman, K. Lai, I. Stoica, and J.
Chuang. Robust Incentive Techniques
for Peer-to Peer Networks. In
Proceedings of the Fifth ACM Conference
on Electronic Commerce, May 2004.
 David Hales, Bruce Edmonds: Applying a
socially inspired technique (tags) to
improve cooperation in P2P networks.
IEEE Transactions on Systems, Man, and
Cybernetics, Part A 35(3): 385-395. 2005.

Cliente servidor vs. P2P
Cliente/servidor
P2P
Tráfico de red
Asimétrico, tráfico de Simétrico.
subida bajo aceptable.
Contenido
Centralizado en el
servidor.
Distribuido entre los
peers.
Direccionamiento
Estático, utilizando
DNS, NAT, puertos
bien conocidos (80).
Dinámico, registros en
tiempo real.
Tratamiento de
NAT/firewall.
Rendimiento
Decrece con el
número de usuarios.
Aumenta con el
número de usuarios.
¡Gracias Javier!
Algunos factores que afectan el
rendimiento

Algoritmo de ruteo.

Grado de replicación de recursos
populares.

Cooperación.
Lo Común o Compartido


Aunque todos se benefician de un recurso
común, el mismo termina siendo destruido por la
actitud egoísta de cada individuo.
Fenómeno bien estudiado por las ciencias
sociales
 sobrepastoreo
de un lote compartido
 contaminación del ambiente
 deforestación
 pesca intensiva
 ...
Tragedy of the Commons
“That which is
common to the
greatest number
has the least care
bestowed upon
it"
Aristóteles
384 BC-322 BC
Tragedy of the Commons
"Freedom in a
commons brings
ruin to all”
"The Tragedy of the
Commons," Garrett
Hardin, Science,
162(1968):1243-1248.
Garrett Hardin
1915-2003
Cooperación

Alta performance
requiere alto grado de
cooperación
 compartir archivos
 más se comparte  menor
latencia
 ruteo
 más se reenvía  menor
latencia, menor pérdida,
mayor conectividad
servicio
(ej., reenvío de paquetes,
descarga de archivos)
servicio
servicio
Motivación
Los sistemas P2P se basan en la
cooperación entre usuarios con intereses
propios.
 Free-Riding/Greedy Behavior.
 Necesidad de incentivos para la
cooperación.

Juegos
 Estrictamente

competitivos (suma cero)
ajedrez, go, póquer, escondidas
Juegos (y otras situaciones)
 Puramente
cooperativos (o casi)
Juegos
 Juegos

Cooperativos/Competitivos
dilema del Prisionero, dilema del contrabandista,
halcón y paloma
Dilema del Prisionero
Alicia
Roberto
confiesa
niega
confiesa
3,3
0,5
niega
5,0
1,1
Dilema del Prisionero
Alicia
Roberto
cooperar
desertar
cooperar
R,R
P,T
desertar
T,P
C,C
R: Recompensa T: Tentación P: Perdedora
C: Castigo
T>R>C>P
R > (T+P)/2.
Torneo de Axelrod (1979)
Invitación a enviar estrategias.
 Los programas (estrategias) compiten
entre ellos.
 Objetivo: obtener puntos.
 Pueden recordar interacciones previas
 14 estrategias + aleatoria

Representación de las estrategias
Autómatas finitos.
 Estados  acciones del jugador.
 Arcos  acciones del oponente.
 Estado inicial  elección inicial del
jugador.

TIT-FOR-TAT “nice”
C
D
C
D
D
C
TIT-FOR-TAT
TAT-FOR-TIT “nasty”
C
D
D
D
C
C
TAT-FOR-TIT
EASY-GO “hopeless”
C
D
D
EASY-GO
C,D
C
FORG-NOT “ruthless”
C
D
C
FORG-NOT
C,D
D
Una Sola Vez vs. Repetidas Veces
El razonamiento a seguir no es el mismo
si se juega una sola vez a si se juega
repetidas veces.
 Estrategias con memoria.
 Más próxima a las situaciones de la vida
real.

La Evolución de la Cooperación


Explorar las
condiciones bajo las
cuales la cooperación
emerge entre agentes
fundamentalmente
egoístas.
Incentivo a largo
plazo para la
cooperación, a pesar
de existir un incentivo
a a corto plazo que
favorece la deserción.
Cooperación Emergente
Torneo ecológico.
 Resultado de un juego tiene influencia en
la proporción con que cada estrategia se
vería representada en el juego siguiente.
 Resultado

 Estrategias
torpes fueron desapareciendo
 Estrategias del tipo TIT-FOR-TAT fueron
sobreviviendo.
 El ambiente resultó ser cada vez más
cooperativo.
Dilema del Prisionero Generalizado

Similar al dilema del prisionero clásico
pero con peers que pueden asumir el rol
de clientes y servidores en cada jugada.
servicio
(e.g., redireccionamiento de paquetes,
descarga de archivos)
servicio
%@#?!
servicio
servicio
servicio
ja,ja,ja.
fuente Incentives for Cooperation in the Internet. Lai et al
Nuevos Desafíos
Gran número de peers  menor
probabilidad de repetir interacción entre
peers.
 Identidades “gratuitas”  cambio
continuo de identidad.
Aumenta la probabilidad de interactuar con
extraños.

Nuevos Desafíos (cont.)

Asimetría  modos servidor y cliente
+7
solicitar servicio
-1
otorgar servicio (cooperar)
?
solicitar servicio
ignorar solicitud
(desertar)
Nuevos Desafíos
Alicia
Roberto
Cliente
confiesa
niega
confiesa
niega
3,3
5,0
0,5
1,1
Servidor
otorgar
solicitar
7,-1
no solicitar
0,0
ignorar
0,0
0,0
Objetivo

Diseñar estrategias de incentivos que

motiven al sistema a alta utilidad
generalizada (por ejemplo., 100%
cooperación)
 brinden mayores beneficios que los
obtenidos al desertar.
Arquitectura
Alicia
Roberto
servicio
historia
compartida
servicio
Alicia: 1 cooperación c/Roberto
Juan: 1 cooperación c/Alicia
Juan
historia
privada
Alicia: 1 cooperación
Estrategia
función de
decisión
Espacio de Diseño

Función de decisión
 uso
de historia compartida y subjetiva.
 trato con extraños.
 robusta ante diferentes patrones de
deserción.
Espacio de Diseño

Historia Privada vs. Historia Compartida
 Privada: A almacena
las acciones de B hacia
A.
poca utilidad si la población es muy grande
(repetición improbable).
 implementación descentralizada directa.

 Compartida:
Se almacenan las acciones de B
hacia todos.

cuestiones de escalabilidad.
Espacio de Diseño

Extraños
 Problema
con identidades no persistentes
 Legitimate newcomer vs. Whitewashers
 Estrategias especializadas para tratar con
extraños.
Espacio de Diseño

Reputación objetiva vs. reputación subjetiva
 Objetiva:

vulnerable a colusión
 Subjetiva

noción de confiabilidad
Espacio de Diseño

Estrategia de Selección
 Evitar
extraños y desertores.
 A veces los servicios sólo están disponibles a
través de un subconjunto de los servidores
(selección limitada).
¿Por qué BitTorrent funciona tan
bien?



Selección Grupal.
BT resiste freeloaders
y soporta altruismo (al
menos en parte)
Grupos con
numerosos
freeloaders tienden a
desaparecer.
Tags para Promover Cooperación
C,D
C,D
C
D
tag
tag
10100010010001000
01101000011001101
TagsWorld
C,D
C,D
C,D
C
D
tag
tag
C
C,D
C,D
C
C,D
tag
tag
D
C,D
tag
tag
D
D
tag
C
C,D
C,D
C,D
D
D
tag
tag
tag
C,D
C
tag
C,D
C
tag
Cooperación Basada en Tags
Conclusiones y Cuestiones Abiertas


Las técnicas de incentivos mitigan pero no
previenen.
Tipo de incentivo
 Incorporado
al algoritmo (upload rate determina
download rate)
 Externo (micro-pagos, puntaje, popularidad, fama).
 Manual (exponer generosidad del usuario)

Los protocolos existentes requieren un cierto
grado de honestidad (son vulnerables)
Descargar

Sistemas P2P y sus Aplicaciones