Sistemas RH. Un artículo reciente relevante.

Disclaimer. Pido disculpas al lector por mezclar en esta entrada cuestiones que no tienen mucho que ver: política local española, artículo técnico de ingeniería de redes, crítica de la normativa del sistema de patentes de EEUU etc…. Narrativa postmoderna oblige

Ya no va a haber nada nuevo con respecto al tema de Cataluña (salvo quizás el debate Margallo-Junqueras que creo es mañana), ni siquiera el día de las Elecciones, y estoy de nuevo concentrado 100% en éste tema y he encontrado éste artículo en el que hablan de un problema muy similar (si no es el mismo) que el que nos hemos planteado en las varias entradas sobre los sistemas RH.

Nota. Recordamos al lector que en un sistema RH, un tipo de sistemas HPC que hemos propuesto nosotros en varias entradas en este blog, a diferencia de lo que es habitual actualmente, todas las comunicaciones entre nodos (punto a punto y colectivas) se realizarían mediante recorridos hamiltonianos. Por ello es de interés diseñar redes que, dado un tamaño o numero de nodos, permitan que múltiples recorridos de este tipo puedan circular en la red simultáneamente sin interferencias.

Teniendo en cuenta la dificultad que suponía, antes de los resultados de nuestra patente incluso determinar si en una red de interconexión dada (modelada por un Dígrafo de Cayley 2-generado) existe un sólo recorrido hamiltoniano, para este tipo de sistemas teóricos que hemos propuesto nosotros es de gran interés un método como el que hemos patentado que sea capaz:

a) tanto de identificar aquellos casos que potencialmente tienen recorridos hamiltonianos, puediendo obtener además una idea aproximada de la cantidad de recorridos hamiltonianos que se podrían obtener. Esto es interesante pues,  incluso utilizando los métodos constructivos de la patente intentar generar un recorrido hamiltoniano tiene un coste en recursos computacionales, sobre todo, aunque no  solo, si no los tiene.

b) como de generar o construir, dada una topología de red de interconexión, múltiples (o si fuese necesario todos los posibles) recorridos hamiltonianos.

En la primera patente queríamos proteger ambos resultados, el  a) y el b). Por motivos puramente normativos (es decir por como se redactaron las claims, no sustanciales) nos concedieron sólo la protección para el segundo.  En la segunda solicitud, la continuation, insistimos para proteger el primer resultado, el a), que son varios pasos independientes del método completo, que tienen un elevado valor por si mismos, y por estar afectados por el caso Alice Corp, que ya si podría añadir razones sustanciales, de nuevo se  ha denegado, aunque en la respuesta al examinador, pienso, quedó claro que estas razones sustanciales no aplicaban a nuestro caso. Pero el examinador, que  pensamos no conoce en detalle la invención, no lo ha considerado así y tenemos que insistir perdiendo más tiempo e invirtiendo un mayor coste.

En una entrada anterior, un ejemplo del tipo de problemas que se estudian para los sistemas RH, muy similares aunque con diferentes objetivos, a los que se plantean en el artículo que reseñamos  en ésta. En ella, utilizando las técnicas de existencia, no constructivas, de la patente,  utilizamos una familia infinita  de Dígrafos de Cayley, el grupo cuaternio generalizado, que cumplen una condición que hemos impuesto para este tipo de sistemas.

Fin de nota.

Me ha gustado sobre todo porque tiene el enfoque ingenieril, y no el de las matemáticas abstractas, y tiene la claridad con la que se suelen expresar los autores chinos, muy diferentes a la confusión rebuscada (intencional o no) con la que se expresan autores de otros países.

Estoy compilando artículos relevantes relacionados con el tema de la patente publicados den 2015 y ya he encontrado algunos. Es posible que  hagamos una entrada sobre ello.

The Property of Edge-Disjoint Hamiltonian Cycles in Transposition Networks and Hypercube-Like Networks.

Ruo-Wei Hung Department of Computer Science and Information Engineering, Chaoyang University of Technology, Wufeng, Taichung 41349, Taiwan

Abstract.

The presence of edge-disjoint Hamiltonian cycles provides an advantage when implementing algorithms that require a ring structure by allowing message traffic to be spread evenly across the network. Edge-disjoint Hamiltonian cycles also provide the edge-fault tolerant hamiltonicity of an interconnection network. In this paper, we first study the property of edge-disjoint Hamiltonian cycles in transposition networks which belong to a subclass of Cayley graphs. The transposition networks include other famous network topologies as their subgraphs, such as meshes, hypercubes, star graphs, and bubble-sort graphs. We first give a novel decomposition of transposition networks. Using the proposed decomposition, we show that n-dimensional transposition network with n > 5 contains four edge-disjoint Hamiltonian cycles. By using the similar approach, we present linear time algorithms to construct two edge-disjoint Hamiltonian cycles on two variants of hypercubes, including twisted cubes and crossed cubes. Keywords: Edge-disjoint Hamiltonian cycles, edge-fault tolerant hamiltonicity, transposition networks, twisted cubes, crossed cubes.

Extractos.

Parallel computing is important for speeding up computation.

The design of an interconnection network is the first thing to be considered.

Many topologies have been proposed in the literature [4, 6, 10, 14, 20, 33, 34, 38], and the desirable properties of an interconnection network include symmetry, relatively small degree, small diameter, embedding capabilities, scalability, efficient routing, and fault-tolerant robustness.

Among those proposed interconnection networks, the hypercube is a popular interconnection network with many attractive properties such as regularity, symmetry, small diameter, strong connectivity, recursive construction, partition ability, and relatively low link complexity [40]. In the literature, many variants of hypercubes have been proposed for enhancing the architecture of hypercubes.

In this paper, we will study the edge-disjoint Hamiltonian cycles property of two variants of hypercubes, including twisted cubes and crossed cubes.

Cayley graphs arise naturally in interconnection networks and, hence, some interesting properties on them have been studied [5, 37, 41]. The transposition networks form a subclass of Cayley graphs and include other network topologies as their subgraphs, such as meshes, hypercubes, star graphs, and bubble-sort graphs [34, 44]. The transposition networks possess many attractive network properties, such as node symmetric [2], regular, sublogarithmic diameter, small fault-diameter, high node connectivity, embedding capabilities of meshes and hypercubes, simple shortest routing [34], lower bisection width [43], efficient node-disjoint path routing [19], and so on.

In this paper, we will investigate the property of edge-disjoint Hamiltonian cycles in transposition networks. The architecture of an interconnection network is usually modeled by a graph in which the nodes represent the processing elements and the edges represent the communication links. In this paper, we will use graph and network, vertex and node, and edge and link interchangeably.

A Hamiltonian cycle in a graph is a simple cycle that passes through every node of the graph exactly once. A graph is called Hamiltonian if it contains a Hamiltonian cycle. The ring structure is important for distributed computing, and its benefits can be found in [29].

Two Hamiltonian cycles in a graph are said to be edge-disjoint if there exists no common edge in them. A graph admits a Hamiltonian decomposition if all of its edges can be partitioned into disjoint Hamiltonian cycles. The edge-disjoint Hamiltonian cycles can provide an advantage for algorithms that make use of a ring structure [39].

Consider the problem of all-to-all broadcasting in which each node sends an identical message to all other nodes in the network. There is a simple solution for the problem using an η-node ring that requires η−1 steps, i.e., at each step, every node receives a new message from its ring predecessor and passes the previous message to its ring successor.

If the network admits edge-disjoint rings, then messages can be divided and the parts broadcast along different rings without any edge (link) contention. 

If the network can be decomposed into edge-disjoint Hamiltonian cycles, then the message traffic will be evenly distributed across all communication links. Edge-disjoint Hamiltonian cycles also form the basis of an efficient all-to-all broadcasting algorithm for networks that employ wormhole or cut-through routing [35].

Further, edge-disjoint Hamiltonian cycles also provide the edge-fault tolerant hamiltonicity of an interconnected network; that is, when a Hamiltonian cycle of an interconnected network contains more one faulty edge, then the other edge-disjoint Hamiltonian cycle can be used to replace it for transmission.

In this paper, we first study the edge-disjoint Hamiltonian cycles property of transposition networks. We show that 4-dimensional transposition network admits a Hamiltonian decomposition, and then show that n-dimensional transposition network with n > 5 contains four edge-disjoint Hamiltonian cycles. Then, we use the same approach to construct two edgedisjoint Hamiltonian cycles in twisted cubes and crossed cubes which are two variants of hypercubes. In the following, we give a briefly survey on transposition networks, twisted cubes, and crossed cubes.

Llevo un cierto tiempo estudiando la respuesta del examinador  a mi segunda  solicitud de patente, y cuanto más la releo menos entiendo el por qué de la final rejection,  teniendo en cuenta la importancia del problema que resolvemos de cara a importantes aplicaciones, como se pone de manifiesto de nuevo en éste reciente artículo  de 2014.

Nota. Tampoco entiendo la posición de otra parte, pero esto me lo callo, pues ya dijimos  que no  íbamos a dar detalles de determinados temas y vamos a ser firmes en ésto. Fin de nota.

Los motivos de la final rejection y los argumentos que  utiliza el examinador me parecen cada vez más absurdos y ya casi puedo confirmar que no se ha leído o no ha comprendido lo que tiene entre manos.

Aún así hay que intentar rebatirlos. Uno se encuentra en la disyuntiva de preparar una respuesta larga bien armada, y que entonces ni la lea ya que tienen sobrecarga de trabajo o  una corta, sucinta, que no explique suficientemente bien mi posición, en cuyo caso la leerá  pero no al comprenderá. Así es la vida del inventor.

Nota. Que ésto suceda en un país como  EEUU, que se supone que es era el país más avanzado (hasta que se han cargado el sistema  de patentes), es muestra suficiente del estado del mundo. Teniendo esto en cuenta todo esto, ¿ que hay de raro en que a un presidente de una Comunidad Autónoma le parezca totalmente natural pervertir de manera criminal el objeto de unas Elecciones Autonómicas; que un conjunto de merecidamente prestigiosos economistas neo-clásicos que dan clases en el país citado y han construido su carrera en base a resultados que indican que el capitalismo, cuyo presupuesto es un Estado de Derecho Democrático, es el mejor sistema, apoyen ésta criminal perversión electoral que además está diseñada y ejecutada por un conjunto de organizaciones vinculadas a la extrema izquierda  comunista; que una multinacional como Google, de ese mismo país, pueda atropellar gratuitamente al usuario y que el sistema  judicial español lo permita, o que un valor como la amistad, tenga hoy un idem nulo ?. Llegados a éste punto, personalmente no espero más que decadencia. Fin de nota.

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: