[DPS Lab] Extra Points 2

• Transition: The process of change from one form, state, style or place to another.
• Event: Is an action that is usually initiated outside the scope of a program and that is handled by a piece of code inside the program. Typical sources of events include the user (who presses a key on the keyboard, in other words, through a keystroke).
• Execution: Is the process by which a computer or a virtual machine carries out the instructions of a computer program. The instructions in the program trigger sequences of simple actions on the executing machine. Those actions produce effects according to the semantics of the instructions in the program.
• Graph: Is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges.
• Interrumption: Is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution. A hardware interrupt causes the processor to save its state of execution and begin execution of an interrupt handler. Software interrupts are usually implemented as instructions in the instruction set, which cause a context switch to an interrupt handler similar to a hardware interrupt.
• Node: A vertex (plural vertices) or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices).
• Disallow: Deny the access or use of something.
• Condition: Is a feature of a programming language which perform different computations or actions depending on whether a programmer-specified boolean condition evaluates to true or false. Apart from the case of branch predication, this is always achieved by selectively altering the control flow based on some condition.
• Input: Any data entered into a computer or data processing system,
• Reachable: Be able to touch or take something with our arms
• Precise: Is a measure of the detail in which the quantity is expressed. This is usually measured in bits, but sometimes in decimal digits. It is related to precision in mathematics, which describes the number of digits that are used to express a value.

[DPS Class] Contributions WEEK 11

This week I did a research about Fault Tolerance for the wiki, in that research I include some general information, concepts about the theme and a simple procedure that we can implement in our distributed system

Link: http://elisa.dyndns-web.com/progra/faultTolerance

For the laboratory I did a research about Petri Nets, here I include some general concepts [Spanish].

Link: http://jcecdps.blogspot.mx/2012/04/dps-lab-red-de-petri.html

Nominations

• Roberto Martinez, because his research about the Petri Net Simulator and my research about Petri Nets complements each other very well
• Cecilia Urbina, because she stills investigating about very good python tools to improve the cluster.

The references are in each page.

[DPS Lab] Red de Petri

Es una representación matemática o gráfica de un sistema a eventos discretos en el cual se puede describir la topología de un sistema distribuido, paralelo o concurrente. La red de Petri esencial fue definida en la década de los años 1960 por Carl Adam Petri. Son una generalización de la teoría de autómatas que permite expresar un sistema a eventos concurrentes. 

Una red de Petri es un grafo orientado con dos tipos de nodos: lugares (representados mediante circunferencias) y transiciones (representadas por segmentos rectos verticales).

Los lugares y las transiciones se unen mediante arcos o flechas.

Fundamentos

• Una Red de Petri es un modelo gráfico, formal y abstracto para describir y analizar el flujo de información.
• El análisis de las Redes de Petri ayuda a mostrar información importante sobre la estructura y el comportamiento dinámico de los sistemas modelados.
• La teoría de las Redes de Petri permite la representación matemática del sistema a ser modelado.
• Las Redes de Petri son de utilidad en el diseño de sistemas de hardware y software, para especificación, simulación y diseño de diversos problemas de ingeniería.
• Las Redes de Petri pueden considerarse como autómatas formales o como generadores de lenguajes formales y tienen asociación con la teoría de grafos.
• Son excelentes para representar procesos concurrentes, así como, procesos donde pueden existir restricciones sobre la concurrencia, precedencia, o frecuencia de esas ocurrencias.

Ventajas

• Tratamiento individual de procesos independientes.
• Procesos paralelos o concurrentes.
• Recursos compartidos.

Estructuras Básicas

Componentes y caracteristicas

Las Redes de Petri están compuestas de cuatro componentes básicos que forman su estructura:

• Un conjunto de plazas P
• Un conjunto de transiciones T
• La función de entrada I
• La función de salida O

Las funciones de entrada y salida relacionan las transiciones y las plazas.

La función de entrada I es un mapeo a partir del conjunto de plazas de entrada hacia la transición tj, la función se puede escribir como I(tj).

La función de salida O es un mapeo a partir de la transición tj hacia el conjunto de plazas de salida, la función de salida se puede escribir como O(tj).

Construcción

1. Un arco une siempre lugares con transiciones y nunca dos lugares o dos transiciones.
2. Una transición puede ser destino de varios lugares y un lugar puede ser el destino devarias transiciones.
3. Una transición puede ser origen de varios lugares y un lugar puede ser origen de varias transiciones.
4. Los lugares pueden presentar marcas (una marca se representa mediante un punto en el interior del círculo).





5. Cada lugar tiene asociada una acción o salida. Los lugares que contiene marcas se consideran lugares activos. Cuando un lugar está activo sus salidas están a uno.
6. A las transiciones se les asocia eventos (funciones lógicas de las variables de entrada). Una transición se dice que está sensibilizada cuando todos su lugares origen están marcados.
7. Cuando ocurre un evento asociado a una transición (la función lógica se hace uno), se dice que la transición está validada.

Validación

Consiste en comprobar que se cumplen las propiedades de vivacidad, limitación y reversibilidad:

Hay que considerar :

M0: marcado inicial. De este se desprende el comportamiento del sistema.

[M0] : vector de marcados posibles a partir de un marcado inicial. (marcados alcanzables).

• Vivacidad: Se trata de un concepto relacionado con la idea de “no bloqueo”. 
  Una transición se dice viva si para un marcado inicial existe una secuencia de franqueos para la cual se puede franquear esa transición. Si todas las transiciones de una red son vivas, la RdP se llama viva y así la red nunca se bloquea.
• Limitación: Se dice que la red está k- limitada si para todo marcado alcanzable tenemos que ningún lugar tiene un número de marcas mayor que k. Las redes 1-limitadas pueden implementarse mediante biestables, estas redes son conocidas como binarias.
  Si la red diseñada generar más marcas que las que su limitación permite el modelado será erroneo
• Reversibilidad: Una RdP es reversible si para cualquier marcado alcanzable es posible volver al marcado inicial.

Referencias

• Redes Petri PDF
• Fundamentos Redes Petri
• Red de Petri Wikipedia

[DPS Class] Contributions WEEK 9

This week I did a research about RPyC or Remote Python Call, that is a library to perform Distributed Computing, Disttibuted Testing, Remote Administration and Tunneling or Chaining.

All the information about this tool is in the following link:

Link: http://elisa.dyndns-web.com/progra/rpyc

I think this is another usefull tool to improve our cluster because, as well we know, python is a powerfull but simple programming languaje, and the most of us know how to code in this languaje.

All the references are also in the Wiki Page.

[DPS Lab] Extra Points

1. Authentication: is the act of confirming the truth of an attribute of a datum or entity. This might involve confirming the identity of a person or software program, tracing the origins of an artifact, ensuring that a product is what its packaging and labeling claims to be.


2. Identity: Is a set of data that uniquely describes a person or a thing (sometimes referred to as subject or entity) and contains information about the subject's relationships to other entities


3. Consistent: When the data in a storage system remains unchanged over a period of time.


4. DistributionThe act of divide the tasks in several computers.


5. Scalable: When a system, network, or process, is capable to be enlarged to accommodate that growth in amount of work and performance.


6. Allocalte: The action of set a portion of a system memory or system storage for specific purposes.


7. Transaction: The act of exchange or transfer something from one place to another.


8. Driver: Is a computer program allowing higher-level computer programs to interact with a hardware device through the system bus.


9. Replica: Is a copy of a system data shared and stored in another computer system.


10. Sorting: Is the act of arrange a set of data in a particular order.


11. Security: Is the degree of protection against danger, damage, loss, and crime.


12. Task: Is an execution path through address space. In other words, a set of program instructions that are loaded in memory. The address registers have been loaded with the initial address of the program. At the next clock cycle, the CPU will start execution, in accord with the program.

[DPS Lab] Consistency and Replication

Replication

"Is the process of sharing information so as to ensure consistency between redundant resources, such as processes, storage devices and systems, etcetera. 

The same data is shared and/or stored in several devices. 

The replication itself should be transparent to an external user. Also, in a failure scenario, a failover of replicas is hidden as much as possible. "

Types

• Active: is performed by processing the same request at every replica.
• Passive: each single request is processed on a single replica and then its state is transferred to the other replicas.

Why perform Replication?

• Enhance reliability
• If one replica is unavailable or crashes, use another.
• Protect against corrupted data
• Improve performance
• Scale with size of the distributed system (replicated web servers).
• Scale in geographically distributed systems
• Key issue: need to maintain consistency of replicated data.

Keeping replicas up to date needs a lot of network use, so, we need a high speed broadband connection between nodes. The updates need to be atomic (transaction) The replicas need to be synchronized (time consuming)

Consistency

Is the process of keep the same information in all the systems all the time.

All the replicas must be consistent, if one copy is modified, others become inconsistent; so:

• Modifications have to be carried out on all copies.
• Problems with network performance.
• It is needed to handling concurrency.

Consistency models are used in distributed systems like distributed shared memory systems or distributed data stores (such as a filesystems, databases, optimistic replication systems or Web caching). The system supports a given model, if operations on memory follow specific rules. The data consistency model specifies a contract between programmer and system, wherein the system guarantees that if the programmer follows the rules, memory will be consistent and the results of memory operations will be predictable. The most common models are:

• Casual Consistency: Writes that are potentially casually related must be seen by all processes in the same order. Concurrent writes may be seen in a different order on different machines.
• FIFO Consistency: Writes done by a single process are seen by all other processes in the order in which they were issued, but writes from different processes may be seen in a different order by different processes.
• Strict Consistency: Any read always returns the result of the most recent write, implicitly assumes the presence of a global clock. A write is immediately visible to all processes.
• Secuential Consistency: Weaker than strict consistency. Assumes all operations are executed in some sequential order and each process issues operations in program order. Any valid interleaving is allowed. All agree on the same interleaving. Each process preserves its program order. Nothing is said about “most recent write”

Consistency Model Comparison

References

• Consistency [pdf]
• Consistencia y Replicacion [pdf]
• Consistencia y Replicacion 2 [pdf]

[DPS Class] Contributions WEEK 8

Last week, the members of the cluster team did a work meeting. We talked about the importance of join our efforts to build only one cluster instead of work separately in small groups.

We decided the specifications of each computer that are in cluster:

• Operating System: Ubuntu 10.04 64bits
• User: cluster
• Password: (1)

Also, we did the schedule of the activities that we need to do to configure the cluster.

1. Install all the software and packages.
2. Configure VPN.
3. Configure a computing grid.

In a second stage, we are going to integrate a website, where will be possible to upload the tasks, which will be validated, executed and processed by the cluster, and at the final we can download the results, maybe in a compressed file.

This task will be done by Emmanuel, with some tools like:

1. Apache, PHP
2. Ruby on Rails
3. Configure a computing grid.

I think this was necessary. Now we are working together and I hope that the results are even more significant than before.

Nominations

• Cecy Urbina: Because she remains active in exam weeks
• Roberto Martinez: Because he remains active in exam weeks
• Rafael Lopez: Because he participate actively in the meeting, distributing task and clarifying doubts.

(1): Check the Google Document posted in our Facebook page to check this information. (Security :P)