XXIX ENDIO y XXVII EPIO 2016

El 2 y 3 de junio de 2016 tuve el honor de participar en el encuentro anual XXIX ENDIO y XXVII EPIO. En el mismo dictamos un seminario sobre “TÉCNICAS METAHEURÍSTICAS DISTRIBUIDAS PARA PROBLEMAS DE RUTEO DE VEHÍCULOS EN ENTORNOS DE GRANDES VOLÚMENES DE DATOS (BIG DATA/IOT)” de 6hs dividiéndolo en dos módulos de 3hs, del cual participaron docentes e investigadores de la UBA, UTN regional BsAs, UCA, UdeMM (Universidad de la Marina Mercante), estudiantes de Ingeniería Industrial de la UBA y profesionales de la Industria (logística y sistemas).

epioendio

Queremos agradecer a todos los asistentes y organizadores. A quiénes hayan asistidos queremos comunicarles que pueden consultarnos por cualquier sugerencia o duda que no hayamos podido tratar durante el dictado del seminario.

 

II JIFICI en la UNGS

A principios de Junio de 2016 tuve el gusto de participar en las II JORNADAS DE INVESTIGADORES EN FORMACIÓN DEL INSTITUTO DE CIENCIAS: La Ciencia y el Tiempo.

Las segundas jornadas tienen como objetivo examinar la vinculación entre la ciencia y el tiempo generando un espacio de diálogo interdisciplinario. Se busca la integración de las diferentes áreas de investigación del ICI para lo cual se propone el abordaje de ejes transversales, como por ejemplo: el hombre y el tiempo; la naturaleza y el tiempo; el tiempo y el método científico; tiempo, técnica y experimentación; la variable tiempo; mitología del tiempo; misceláneas del tiempo. La propuesta no busca trabajos que necesariamente pertenezcan a un tema/área de investigación específico del instituto, sino reflexionar sobre las diferentes formas en que el tiempo es tomado por cada disciplina.

El programa de las jornadas está disponible en el link.

Fue muy enriquecedora la interacción entre investigadores de áreas tan diversas como computación, química, matemática, educación, historia y sociología.

El tema de mi breve exposición fue El concepto de Tiempo Real vinculado a problemas de
Optimización Combinatoria que involucren grandes volúmenes de Datos. Particularmente ilustrado con el tratamiento del problema del ruteo de vehículos (VRP) en entornos de grandes volúmenes de datos, tal como se comenta aquí. Compartí mesa con Ana Janeiro que expuso sobre catalizadores (química) y su investigación, que realmente es muy importante. Lamentablemente no pude quedarme a escuchar la mesa de Judith Faifman y Matías Wersocky sobre las conceptualizaciones de la temporalidad en las relaciones entre Estado – Estructura productiva – Infraestructura científica-tecnológica dentro del sector de software y servicios informáticos durante el período 2003 a 2015 en Argentina. Sobre esto último espero poder ponerme al tanto invitando uno o más cafés….

Lambda Route Una propuesta para optimizar rutas vehiculares urbanas de forma centralizada y en línea

En marzo de 2016 publicamos dentro del Call for papers promovido por el BID “Nuevos debates: Datos para el desarrollo” en yogobierno.org.

El artículo calificó 3ro en la convocatoria, y fue publicado tanto por la plataforma digital de yogobierno, como en el blog Gobernarte del BID.

El objetivo de la propuesta (llamada “Route”) es proveer a una ciudad (o una zona urbana más extensa) de una plataforma centralizada y fiable para el estudio y el ajuste constante de las rutas de distribución y servicios capaz de:

  • Procesar un modelo complejo de predicción de tráfico a partir de información histórica masiva provista por elementos de la red de transporte, como semáforos y cabinas de peaje, así como información proveniente de dispositivos IoT distribuidos en los vehículos,
  • Proveer soporte para novedades en línea producidas en la red de tránsito que afecten las rutas resultantes.

Cabe destacar que algunos componentes importantes de la presente propuesta, como la aplicación de Algoritmos Genéticos Distribuidos y el correspondiente estudio del speed up se han prototipado y validado en los laboratorios de la Universidad Católica Argentina.

El link al artículo: Lambda Route.

¿A qué se refiere Big Data?

El concepto de “Big Data” está relacionado con las tecnologías que permiten el procesamiento1 de grandes volúmenes de información, entendiéndose como grandes los volúmenes que por su tamaño o complejidad están por fuera del alcance de las herramientas de procesamiento de datos tradicionales.

A mediados de 2013 se ha hecho de público conocimiento el análisis de las comunicaciones masivo que realizaron agencias asociadas al gobierno de los Estados Unidos con el fin de monitorear o espiar actividades de habitantes de dicho país o de otros países del mundo. Fue entonces cuando el concepto de “Big Data” tomó un estado público que no tenía anteriormente, dado que este tipo de análisis fue realizado con herramientas relacionadas con dicho paradigma. Por lo tanto, es muy difícil, a partir de dicho hallazgo, darle el tinte únicamente tecnológico (o tecnocrático si se desea) que “Big Data” acarrea (cuyos principales elementos son objetivamente tecnológicos).

Si generalizamos este último razonamiento al ámbito de la tecnología como un todo, encontraremos que no se trata de un caso nuevo, ya que como se afirma en [Feenberg, 2002] en su teoría crítica, la tecnología no es una “cosa” (en el sentido más ordinario de dicho término), sino un proceso ambivalente de desarrollo suspendido entre diferentes posibilidades. Esta ambivalencia puede ser distinguida de la neutralidad tecnológica por el rol que esta atribuye a los valores sociales en el diseño de los sistemas técnicos (y no meramente en su uso o consumo).

Académicamente los principales impulsores de las tecnologías de procesamiento masivo de datos son Universidades, e Institutos. Comercialmente, corporaciones como Google, Yahoo, Amazon y Microsoft han dedicado recursos a la investigación en esta área. Usuarios de privilegio de estas tecnologías son las redes sociales: Facebook, Linkedin y Twitter (cuya existencia sería muy difícil sin las tecnologías Big Data), institutos científicos (investigación farmacológica, genética o aceleradores de partículas) o empresas con procesamiento masivo de datos o documentos como China Mobile o The New York Post.

Antecedentes

En principio fueron las actividades de investigación científica (relacionadas, por ejemplo, con biología molecular, telescopios, aceleradores de partículas, meteorología, etc.) las que han requerido de un nivel de procesamiento en volumen de datos fuera de la escala habitual (en el ámbito comercial) de su época.

El incremento en el tamaño de las bases de datos que es factible procesar tiene una explicación tanto en el aumento de la capacidad de cómputo, así como, en el incremento de la posibilidad de almacenamiento y acceso (dispositivos de almacenamiento). Justamente, el sentido de almacenar información relativa a determinados eventos o sucesos de una organización tiene un correlato con el costo o posibilidad de procesamiento disponible. Vale decir que muchas disciplinas (sobre todo en la minería de datos) han surgido por el hecho de que se “hizo” factible el tratamiento de determinada información. Gran parte de esta “información nueva” puede deberse a una necesidad concreta, pero otra parte debe su existencia a la generación de una necesidad artificialmente creada por la disponibilidad de tecnología para su procesamiento.

A mediados del siglo XX [Rider, 1944] se estimó que el crecimiento de las bibliotecas de las universidades de los Estados Unidos se doblaban en tamaño cada 16 años, con lo que se concluyó que en en el año 2040, la Universidad de Yale podría contrar con una biblioteca de 200.000.000 de volúmenes. Lo que requeriría un plantel de 6.000 personas para su mantenimiento. Este tipo de crecimiento viene aparejado con un cambio de paradigma tecnológico.

Paradigma y cambio

El foco de los sistemas tradicionales de procesamiento distribuido ha sido puesto sobre la computación de los problemas (lo que resulta obvio, ya que vinieron a resolver problemas de computabilidad), pero en un marco de gran complejidad de datos (tanto por cantidad, como por relaciones), es necesario enfocarse más sobre los datos.

El paradigma de procesamiento de información clásico instalado por la industria a partir de 1970 fue el modelo relacional de bases de datos, fuertemente sustentado en la teoría de conjuntos y en los predicados de primer orden de la lógica.

Las implementaciones físicas de dicho paradigma, con algunas diferencias con el modelo relacional teórico2, comenzaron a presentar complicaciones en el procesamiento de grandes volúmenes de datos. El escalamiento en este tipo de productos consiste en la implementación de un servidor de mayor potencia. La paralelización de las operaciones se ve afectada por varios de los mecanismos que implementan estos sistemas gestores de bases de datos relacionales para garantizar lo que se conoce como las propiedades ACID3. Esto último constituye un desafío de escalamiento que los motores de bases de datos relacionales no han podido sortear. Incluso las soluciones comerciales que mejoran el rendimiento en este aspecto se basan en la potenciación de un único núcleo de procesamiento (una especie de mainframe) que evitan buscar una solución computacional al problema de la merma del speed up en soluciones realmente paralelas. Cabe destacar que una máquina de 8 veces las capacidades de una PC standard de escritorio cuesta mucho más que 8 Pcs (de hecho, mucho más que 16 Pcs) y es lo que ocurre con este tipo de soluciones.

Es por eso que muchas veces se puede considerar a estas herramientas tradicionales como inadecuadas para tamaños o complejidades tan grandes. Hay modelos de programación que encajan mejor con determinados problemas. Hay, también, modelos de bases de datos que encajan mejor con el entorno y el ciclo de vida del proyecto en cuestión, como por ejemplo las bases de datos orientadas a objetos. Dichas bases de datos se llevan mucho mejor con el paradigma de orientación a objetos4 que las bases de datos relacionales.

Existe un movimiento desde fines de la década de 1990 llamado No SQL5 que principalmente se centró en los problemas de escalabilidad horizontal de las bases relacionales. Los desarrollos dentro de esta iniciativa tienen la particularidad de no cumplir con alguna de las cuatro propiedades ACID6 que sí cumplen las bases de datos relacionales con creces, además de que muchos de los proyectos se originó en el ámbito de la computación distribuida, por lo que no es casual que en el año 2002 se haya presentado una demostración formal del teorema de Brewer7.

El éxito de muchas de estas herramientas en el procesamiento de grandes volúmenes o complejidades de datos no sólo radica en la forma alternativa de modelarlos, sino en el alto nivel de paralelismo que pueden ofrecer. Para poder implementar este nivel de paralelismo se han acuñado una serie de propiedades paralelas a las ACID que permiten este crecimiento.

Referencias

[Feenberg, 2002] “Transforming technology – A critical theory revisited” – Andrew Feenberg – Oxford University Press

[Rider, 1944] “The scholar and the future of the research library” – Freemont Rider

Notas

1Tanto sea la captura, homogeneización, almacenamiento, búsqueda, compartimiento, transferencia o visualización de la información.

2Las diferencias tienen que ver a veces con imposibilidades de implementación física de determinados procedimientos como por ejemplo la utilización de multiconjuntos en lugar de conjuntos; otras veces, con la diferencia en el lenguaje de operación, que en el modelo relacional puede tratarse del álgebra o cálculo relacional y en la implementaciones físicas, con el lenguaje SQL (estándar de facto de la industria)

3Atomicidad: La ejecución de cada transacción debe ser atómica, es decir, o todas las acciones (dentro de la transacción en cuestión) se completan exitosamente o ninguna de ellas se completa, pero nunca puede quedar un estado intermedio, de modo que el usuairo no debe preocuparse por el efecto de transacciones incompletas. La base de datos garantiza ninguna transacción puede quedar “por la mitad”, aunque sea removiendo o volviendo atrás los cambios que quedaron “a medio hacer”. Consistencia: cada transacción debe preservar la consistencia de la base de datos, su integridad. Es la propiedad por la cuál una transacción siempre comienza en una instancia de base de datos consistente, por más que se encuentre (el DBMS) en “el medio” de la ejecución de otra transacción. Aislamiento: el usuario entiende que una transacción corre “sola” sin considerar el ruido que pueda hacer otra transacción ejecutándose en el mismo momento, es decir, las transacciones corren aisladas, o protegidas de los efectos de modificaciones concurrentes. Durabilidad: una vez que el DBMS le confirma al usuario que su transacción ha sido exitosa, sus efectos han sido persistidos (incluso si hay una falla del sistema).

4 Cabe destacar que la industria impuso las bases de datos relacionales, por lo que en los últimos 15 años han surgidos especificaciones de ORM (JPA de Java) y herramientas Open Source como Hibernate (la más popular) que pueden disimular las diferencias de modelos.

5 Que a veces es interpretado como Not Only SQL y que a veces se sugiere que debiera ser No Rel. Y que según sus integrantes vino a compartir como ellos habían logrado derrocar la tiranía de las lentas y caras bases de datos transaccionales a favor de una manera más eficiente y barata de manejar datos.

6 Atomicidad, Consistencia (Integridad), Aislamiento y Durabilidad.

7 También conocido como Teorema CAP, establece que es imposible que un sistema distribuido pueda dar simultáneamente estas tres garantías: Consistencia (todos los nodos ven la misma información), Disponibilidad (la falta de un nodo no impide al resto seguir funcionando) y Tolerancia a Fallos (Partition Tolerance, el sistema sigue funcionando a pesar de pérdidas arbitrarias de información o fallas parciales del sistema). Según el teorema sólo se pueden satisfacer dos simultáneamente de las tres.