Un Problema de Conjuntos en Computación Distribuida1
Esteban Meneses,
Francisco J. Torres-Rojas Resumen:En Matemática existen muchos problemas que involucran conjuntos. Generalmente,
estos problemas están relacionados con un grupo de elementos que deben cumplir
una cierta propiedad. Por ejemplo, los conjuntos pitagóricos son aquellos de la forma
Palabras claves: conjuntos, algoritmo, elojes vectoriales, clases P y NP
IntroducciónLa historia de las matemáticas recuerda con respeto a muchos hombres, uno de ellos es Georg Ferdinand Ludwig Philipp Cantor, creador de la Teoría de Conjuntos. Alrededor de 1873, Cantor descubrió esta apasionante rama de estudio, formalizando de paso la noción de infinito, que hasta el momento había sido solamente una forma de hablar. La Teoría de Conjuntos sirve como base para muchas otras ramas matemáticas, como Probabilidades, Álgebra, Análisis y Ecuaciones Diferenciales. Mas aún, junto con el Cálculo de Predicados, constituye el fundamento de las Matemáticas. En Ciencias de la Computación, la Teoría de Conjuntos también juega un papel preponderante en la Matemática Discreta, Teoría de Computabilidad, Algoritmos, Programación y Especificación Formal de Software. La Teoría de Conjuntos es la responsable de teoremas elegantes y poderosos, como el Axioma de Elección. Empero, en Computación Distribuida existen también problemas interesantes de conjuntos. Tal es el caso de los Conjuntos Imposibles de Relojes Vectoriales ([9]). Este artículo ofrecerá un reto con respecto a este problema. El objeto de estudio de la Teoría de Conjuntos son los conjuntos. Estas entidades matemáticas son objetos que ayudan a representar conceptos. Por ejemplo, si las longitudes de los lados de un triángulo rectángulo son enteras, entonces, esas longitudes se convierten en una terna pitagórica, una especie particular de conjunto.
Una vasta cantidad de problemas en Teoría de Conjuntos se fundamentan
en determinar si el conjunto cumple o no con una
propiedad. Tal es el problema de los conjuntos
balanceados. Un conjunto de números enteros se dice balanceado si
la suma de los elementos es igual a su producto. De esta forma, En Computación Distribuida, cualquier ejecución produce una historia distribuida de eventos. Si se coleccionan las etiquetas vectoriales de esos eventos, se obtiene un conjunto de vectores de enteros, al que se le denominará conjunto posible. Sin embargo, no cualquier conjunto de vectores de enteros es el producto de los eventos de una historia distribuida. A estos conjuntos se les llama imposibles. Descubrir si un conjunto de vectores de enteros es posible o no, es un problema interesante. Existe un algoritmo que resuelve este problema, con el bemol de ser ineficiente. ¿Existirá entonces algún algoritmo eficiente que lo resuelva? En la sección 2 se presenta un modelo de computación distribuida. Los relojes vectoriales, como mecanismo de temporización, se analizan en la sección 3 y en la sección 4 se explica el problema de los conjuntos imposibles. Un mecanismo para clasificar la eficiencia de los algoritmos se ofrece en la sección 5, para dejar las conclusiones al final.
Revista digital Matemática, Educación e Internet.
|
, con 
tales que conforman una terna pitagórica:
. Sin embargo, el algoritmo para determinar si un
conjunto de cardinalidad 3 es pitagórico o no, es muy eficiente. En
Computación Distribuida existen también problemas de conjuntos. Uno
de ellos es el problema de los conjuntos imposibles de relojes
vectoriales ([
es balanceado, pero 
no lo es.