View
3
Download
0
Category
Preview:
Citation preview
Incentivos em Sistemas P2PMarcos Massayuki Kobuchi
IntroduçãoServer Based Peer to Peer
IntroduçãoRedes P2P
● Napster (1999)● Gnutella (2000)
Napster
Gnutella
Características● Grande escala● Alta rotatividade● Anonimato
● Interações entre usuários que nunca irão se encontrar novamente!
Problema● Cooperação dificultada
Agravada por:● Deserções Indetectáveis● Criação de múltiplos usuários
DefiniçõesJogadores:● Peer: podendo ser cliente ou servidor● Seeder: servidor
p2p File Sharing GameObjetivo: aumentar banda de uploadPeer:● Cliente● Servidor
Servidor tem o custo de uso da CPU e banda!
Estratégia DominanteCliente:● Faz downloadServidor:● Se recusa a fazer upload
Free Riding!
Tit for TatRetaliação Equivalente● Dilema do Prisioneiro Iterado
● Ações anteriores são lembradas● Se oponente colaborou, então colaboro● Senão, não.
Shadow of the Future● Jogador fará upload● Expectativa de fazer download no futuro
Problemas:Jogadores farão outras transações?Jogadores terão papéis invertidos?
População Pequena
População Grande
Motivos?Interações entre pares não são frequentes
Reciprocidade Direta não é recomendada:● pareamento randômico● populações grandes
Reciprocidade Indireta?
Soluções● Reputação● BitTorrent● Moeda
Reputação● Histórico dos jogadores
● Recompensar bom comportamento● Punir mau comportamento
KaZaA File Sharing
KaZaA File Sharing● Constrói reputacão com upload de arquivos● Recompensa: prioridade quando download
Estratégias similares para:● armazenagem p2p● multicast p2p● redes adhoc
Esquema de reputação p2pCom técnicas de segurança, podemos:● identificar● isolar● evitar
peers maliciosos!
VulnerabilidadesMultiple colluding peers● melhorar reputação com falsas
recomendações● punir um peer com falsas acusações
Pseudônimos “baratos”● Whitewashing● Sybil Attack
A Minimalist p2p Model● população de peers racionais● diferentes disposições de contribuir● cada peer i tem tipo Ɵi refletindo sua
generosidade ou custo máximo● cada peer faz decisões autônomas:
○ quando contribuir?○ free ride?
A Minimalist p2p Model● custo para cada contribuidor?
○ carga do sistema○ inversamente proporcional a fração de
contribuidores○ Ɵ = 1/x
● peer:○ se Ɵi > 1/x, contribua○ senão, free ride
Free Market● x = Pr(Ɵi ≥ Ɵ)● x = 1/Ɵ● Três equilíbrios:
○ Intersecção○ x = 0
Calculando x...● x = Prob(Ɵi ≥ 1/x)● no caso em que generosidade dos peers
estão uniformemente distribuídos entre 0 e Ɵm
● Prob(Ɵi ≥ 1/x) = 1 - (1/xƟm)● Equação de Ponto Fixo x = 1 - (1/xƟm)● Soluções:x1,2 = (Ɵm ± √(Ɵm^2-4Ɵm))/2Ɵm● se Ɵm < 4 não há x1 estável● x1 tende a 1 quando Ɵm -> ∞
Benefícios do Sistema● Benefícios é proporcional ao nível de
contribuição do sistema● Função αx
○ α grande, onde x=0 é socialmente ineficiente
Performance do Sistema● Diferença entre total de benefícios e custo
de contribuição total● Ws = αx - (1/x)x = αx - 1
● Performance do sistema é limitada pelo menor nível de contribuição
● Sistema entrará em colapso se generosidade máxima for baixa!
Reputação eServiço de Diferenciação● Sistema que pega free riders com
probabilidade p● Política de Diferenciação onde free riders
são excluídos do sistemaOu….● Sistema que consegue diferenciar
perfeitamente free riders de contribuidores● Política de Diferenciação onde free riders
receberão serviço 1-p vezes de um contribuidor
Consequencias● A penalidade introduz uma ameaça a free
riders, induzindo-os a contribuir● Diminui o custo do sistema
○ para x + (1-x)(1-p)○ custo de contribuição [x + (1-x)(1-p)]/x
Um pouco de matemática...● Q: Benefício Individual● R: Custo de Contribuição (reduzido)● T: AmeaçaPerformance:● Contribuidor: Q-R = αx - [x + (1-x)(1-p)]/x● Free rider: Q-T = αx - pαx
Mais um pouco...● Novo equilíbrio de contribuição:
○ x = Prob(Ɵi ≥ R-T) ● = Prob(Ɵi ≥ [x + (1-x)(1-p)]/x - pαx)
● Performance do Sistema○ Ws(p) = x(Q-R) + (1-x)(Q-T)
● = (αx-1)(x+(1-x)(1-p))
Visualizando...
Algumas conclusões● Imposição de penalidade, enquanto
aumenta o nível de contribuição acarreta em alguma perda social
● Podemos ajustar valor de p para conseguir um nível de cooperação desejada○ Se p for suficientemente alto, T > R e não haverá
free riders, atingindo performance ótima
BitTorrent● Barter Based System (Permutação)● Reciprocidade Direta
Arquivo:● dividido em pedaços pequenos pelo seeder● diferentes pedaços para diferentes peers● cada peer troca pedaços com outros peers● peer reconstrói arquivo Swarming Download ou Parallel Download
BitTorrentForçar varias transações entre peers
Exemplo:● Peer inicia download● Carrega conjunto de 40 peers● Seleciona quatro peers para se conectar● Periodicamente atualiza a lista de vizinhos
com peers com melhor taxa de download
ProblemaE depois do download ser concluído?Não há incentivo!
Solução:Reputação!
Outros problemas…● fingir possuir banda de upload menor
enquanto mantem ordem relativa com relação à taxa de upload de outros peers
● sybil attack (aumentando chances de ser selecionado para download)
● whitewashing● enviar “lixo” para aumentar taxa de upload
Moeda (currency)Ganhar crédito contribuindo com recursos….
para gastar comprando recursos!
Currency Based Systems● Mojonation● Karma
Golle et al. (2001)● cada peer faz decisão independente em
relação a sua quantidade de download/upload
● se cada peer é cobrado um valor proporcional a diferença entre download e upload….
● … existe um unico e estrito equilíbrio de nash onde todos peers irão maximizar quantidade de download e upload
Outros comportamentos...Não há só o free riding!
Decisões estratégicas:● ao entrar ou sair da rede● quais peers se conectar● reportar corretamente ao sistema
informações (ex: custos)● manipular mecanismos ou protocolos do
sistema
Hidden Action● ações do peer são ocultas de outros peers● como peers se comportarão?Esperamos que peers enviem e encaminhem mensagens de/para seus vizinhosExemplo:● peer recebe query de um vizinho● responde se possível● encaminha para seus outros vizinhos
Hidden ActionPeer pode:● não enviar a mensagem● enviar probabilisticamente
para reduzir custos!
Um sistema em que todos decidem não enviar pararia de funcionar!
The Principal-Agent Model● Dirigente emprega agentes● Conjunto N de n agentes● Conjunto A = (0, 1) de ações● Cada agente i ∈ N
○ tem ação ai ∈ Ai○ custo c(ai) ≥ 0 para cada ação ai
■ baixo esforço (ai = 0): custo 0■ alto esforço (ai = 1): custo c
The Principal-Agent Model● Coletiva e probabilisticamente, ações dos
agentes determinam uma saída o ∈ {0, 1}● Saída é determinada de acordo com:
○ a tecnologia do projeto○ ou uma função de sucesso t: A1 x … x An → [0, 1]
● Ganho do dirigente:○ v = 0 se saída for 0 (falha)○ v > 0 se saída for 1 (sucesso)
Read-Once Networks● Grafo com dois nós especiais:
○ Source○ Sink
● Cada agente controla uma aresta○ se fizer baixo esforço, probabilidade de sucesso γ○ se fizer alto esforço, probabilidade de sucesso δ≥γ
● Projeto se tiver caminho source-sink● Mapeamento dos sucessos individuais
através de tecnologias○ tecnologia “AND”○ tecnologia “OR”
Probabilidade e Esforço● Um agente:
○ low: probabilidade γ ∈ (0, 1/2) de sucesso○ high: probabilidade 1-γ ∈ (1/2,1) de sucesso
Tecnologia “AND”Probabilidade de sucesso
Tecnologia “OR”Probabilidade de sucesso
ContratosDirigente fará contrato com agentes● Se projeto tem sucesso, pago pi ≥ 0 a cada
agente i● Senão, não pago nada
Pensando em um jogo...Profile of Action● a = (a1,...,an)Utilidade de cada agente:● ui(a) = pi * t(a) - c(ai)
Utilidade do dirigente:
● onde a1,...,an estão em equilíbrio de Nash
Incentivo e ContribuiçãoQueremos motivar todo agente a se esforçar
Contribuição marginal do agente i:
● aumento na probabilidade quando esforça
Melhor estratégiaMelhor estratégia do agente i é:● ai = 1 se
● ai = 0 se
Melhores ContratosOs melhores contratos para o dirigente é:● pi = 0 para agente i que não se esforça● para agente i que se esforça
ObservaçõesNo caso não observável, pagamento de cada agente i é maior que o custo dele!
Price of UnaccountabilityPOU(t)● pior taxa entre
○ utilidade do dirigente no caso observável○ utilidade do dirigente nas ações ocultas
ResultadosLema:● Para qualquer tecnologia t, a utilidade
esperada do dirigente nos contratos ótimos, a probabilidade de sucesso e o pagamento esperado são todos não decrescentes com o valor v
ResultadosPara qualquer tecnologia AND com n agentes
existe um preço v* < ∞ de forma que● qualquer v < v* ótimo é não contratar● qualquer v > v* ótimo é contratar todosPrice of unaccountability:● ponto de transição do caso não observável
ResultadosPara qualquer tecnologia OR com n agentes● existem valores finitos positivos
v1 < v2 < … < vn tal que para qualquervk < v < vk+1
contratar exatamente k agentes é ótimoPrice of unaccountability:● POU é limitado por 5/2
Conclusões● A rede p2p precisa de contribuidores● Racionalidade x Bem Estar Social● Mecanismos
○ Reputação○ BitTorrent○ Moeda
● Hidden Actions● Facilidade de implementação levou ao
florescimento de sistemas p2p● Validação de designs de incentivos
Dúvidas?
Recommended