Skip to content

Diseño y modelización algorítmica de mecanismos distribuídos

Publicado por Sergio Hernando el 22 julio 2006

La frontera entre computación y aspectos económicos es muy difícil de cuantificar en algunas ocasiones. De hecho, muchos modelos económicos se están utilizando en programación y generación de infraestructuras, y viceversa, si bien existe un debate, abierto hace muchos años, para tratar de ver dónde está la frontera entre ambos elementos.

Al hilo de estos conceptos, hay un campo donde es especialmente tangible la mixtura entre economía y técnicas computacionales. Es la algoritmia, cuyos preceptos se usan indistintamente ambas disciplinas, y cuyos resultados de la aplicación están más que demostrados a estas alturas.

Recientemente he tenido acceso a un documento, con cierta solera, de los profesores Noam Nisan y Amir Ronen, que ilustra perfectamente esto de lo que os hablo. El documento se llama Algorithmic Mechanism Design, en el cual se trata el diseño de sistemas distribuídos y cómo los factores comportamentales pueden hacer que los modelos que se creen sólidos, inexpugnables, y strategyproof, es decir, a prueba de estrategias (incluídas las de engaño), resulten no serlo. Un error principal a la hora de plantear un modelo es pensar que los clientes, el público al que se ofrece el sistema, no tiene capacidad para tratar de buscar su propio aprovechamiento, y pensar que todos respetarán las reglas del juego. Nada más lejos de la realidad.

Pensemos, en este mismo blog. Si quiero modelizar el comportamiento de los usuarios, no puedo caer en el error infantil de pensar que vosotros, lectores, sois borreguitos que seguís normas y reglas. Más de uno, y así lo demuestran los logs diariamente, busca su propio aprovechamiento tratando de saltarse las reglas. Los intentos de intrusión, la manipulación, la búsqueda de problemas de programación y un interminable etcétera de situaciones en las que el usuario, por naturaleza humana, se salta las reglas y va a lo suyo.

Si en vez de este blog hablamos de un sistema distribuído con dependencias, la cosa puede tornarse complicada, ya que los comportamientos no previstos en la implementación pueden hacer que el sistema no rinda como es debido, o que sencillamente, deje de rendir. Un buen ejemplo, no perteneciente al campo de las acciones maliciosas, es el problema del rutado.

A la hora de transmitir información, con implicaciones económicas (gasto importante de ancho de banda, priorización por clientes de pago y clientes que no pagan, niveles de servicio mínimo establecidos por contrato, por ejemplo), es frecuente hacer una reserva de ancho de banda que cubra aspectos relacionados con la calidad de servicio. Si confiamos en el comportamiento natural de un router, quizás no se tengan en cuenta estas reservas, motivo por el cual hay que hacerse con el control de las operaciones de rutado, anteponiendo nuestro criterio de calidad de servicio al interés particular de los mecanismos de routing, que actuarán, si no se les dice lo contrario, de un modo egoísta. Una cosa parecida pasa en los sitemas distribuídos de balanceo de carga. Ambos ejemplos vienen citados en el paper.

Tal y como reza el abstract, la motivación de este trabajo de investigación surge ante el planteamiento de sistemas distribuídos, en los cuales no es posible asumir que los participantes sigan a pies juntillas los procedimientos dictaminados por los algoritmos para otra cosa que no sea su propio interés. El documento expone la situación, y ofrece soluciones de incentivo para que los participantes actúen según los designios del implementador, y no de un modo egoísta. Esto es especialmente útil cuando se planifica un servicio distribuído en el que caben este tipo de comportamientos, que si son planificados desde una óptica tradicional simplista del tipo cosas que entran-cosas que salen, serán deficientes y fallarán.

La autoría del paper, sin duda alguna excelente, es de los profesores Noam Nisan, del Institute of Computer Science, de la Universidad de Jerusalén y el School of Computer Science. Como coautor, el profesor Amir Roneny, también del Institute of Computer Science. Este trabajo de investigación, repito, excelente, es el resultado de la financiación del Ministerio de la Ciencia y Tecnología Israelí y la Academia Israelita de las Ciencias, dos instituciones de la máxima categoría internacional en resultados de investigación, con lo que me voy a permitir el lujo de, una vez leído el documento, creer lo que me dicen.

Y es que lo bueno que tienen las matemáticas es que cuando te demuestran con solvencia que 1 y 1 son 2, no caben interpretaciones. Es la diferencia entre las ciencias exactas y la clarividencia.

Desde estas líneas, agradezco al profesor Nisam el trato y la autorización recibida para compilar el Postcript original y ofreceros un formato PDF, servido desde mi máquina, y que podéis descargar si lo deseáis.

Be Sociable, Share!

Categoría/s → Metodos Matematicos

Sin comentarios

Escribir un comentario

Note: XHTML permitido. Tu email nunca será publicado.

Suscribirse a los comentarios via RSS