Vulnerabilidade no protocolo de mictório
Transcrição
Vulnerabilidade no protocolo de mictório
Vulnerabilidade no protocolo de mictório Randall Munroe XKCD, a webcomic of romance, sarcasm, math and language (Publicado originalmente: 2 de setembro de 2009) Quando um cara vai ao banheiro, qual mictório ele escolhe? A a maioria está familiarizada com o Protocolo Internacional de Escolha de Mictório. Ele é discutido exaustivamente em outros lugares, mas a premissa básica é que o primeiro cara escolhe um mictório extremo e cada um que chegar escolhe o mictório que o coloca mais longe de qualquer outra pessoa urinando. Pelo menos um mictório de intervalo é exigido ou Esquisitice se implanta. I. APRESENTAÇÃO DO PROBLEMA Vamos olhar para a eficiência desse protocolo em acomodar todos em mictórios aceitáveis. Para alguns números de mictórios, este protocolo leva a uma acomodaçào eficiente. Se há cnco mictórios, eles se preencherão como na Fig. 1(a). Os primeiros dois caras pegam as extremidades e o terceiro pega o do meio. Neste ponto, os mictórios estão congestionados — nenhum cara pode urinar sem Esquisitice. Entretanto, é bastante eficiente: mais de 50% dos micitórios são usados. na Fig. 1(c). Então uma fileira de oito mictórios apresenta uma eficiência maior que uma fila de sete e uma fila de cinco é melhor que as duas. II. DESENVOLVIMENTO DO MODELO Isso leva a uma questão: qual é a fórmula geral para o número de caras que vão preencher N mictórios se eles chegarem um a um e seguirem o Protocolo? Seria possı́vel escrever um programa recursivo simples para resolver esse problema, mas também há uma expressão fechada. Se f (N ) é o número de caras que podem usar N mictórios, então, para N > 2, ¶ µ 3 f (N ) = 1+2blog (n−2)−1c +max 0, n − 2blog n−2c − 1 . 2 (a)5 mictórios O protocolo é vulnerável à produção de resultados ineficientes para alguns números de mictório. Alguns números permitem empacotamento eficiente e outros levam a uma ocupação esparsa. Se graficarmos a eficiência f (N )/N , obtemos a Fig. 2 (b)7 mictórios (c)8 mictórios Figura 1: Efeito do número de mictórios na acomodação de usuários Por outro lado, se há sete mictórios, eles não se prenche de maneira tão eficiente, como mostra a Fig. 1(b). Deveria haver espaço para quatro caras sem Esquisitice, mas uma vez que o terceiro cara seguiu o protocolo e escolheu o mictório do meio, não há opções para o quarto, que provavelmente vai usar uma cabine — ou a pia. Para oito mictórios, o protocolo funciona melhor, como Figura 2: Eficiência de ocupação em função do número de mictórios Isso sgnifica que alguns números grandes de mictórios vão ser ocupados eficientemente (50%) e outros ineficientemetne (33%). Os “melhores” números de mictórios, correspondentes aos picos no gráfico, são da forma N = 2k + 1 e os piores são dados por N = 32 2k + 1. 2 III. DISCUSSÃO Assim, se você pretende que os usuários ocupem eficientemente seus mictórios, deve haver 3,5,8,17 ou 33 deles e se você pretende tomar vantagem do protocolo para maximizar a esquisitice, deve haver 4, 7, 13 ou 25 mictórios. Esses cálculos sugerem outras aplicações. Rapazes: se vocês entrarem em um banheiro com um número esquisito de mictórios vazios, em vez de ocupar um da extremidade, você pode ocupar um que esteja a um terço [1] Munroe, R, Urinal protocol vulnerability http://blag.xkcd. com/2009/09/02/urinal-protocol-vulnerability/,XKCD blag post (2009) da largura. Isso vai quebrar a série esquisita em duas séries ótimas, transformando o pior caso num caso ideal. Por outro lado, se você quiser criar Esquisitice e o banheiro tem um número não esqisito de mictórios, você pode ocupar aquele a um terço da largura e converter uma fila ótima em duas filas esquisitas. E, claro, se você quiser tornar as coisas realmente esquisitas, sugiro que imprima este artigo e tente explicá-lo para o cara urinando do seu lado.