Idempotencia - Idempotence

Botones de encendido / apagado del panel de control de la señal de destino de un tren . Pulsar el botón On (verde) es una operación idempotente, ya que tiene el mismo efecto ya sea que se haga una o varias veces. Asimismo, presionar Off es idempotente.

Idempotencia ( UK : / ˌ ɪ d ɛ m p t ən s / , Estados Unidos : / ˌ d ə m - / ) es la propiedad de ciertas operaciones en matemáticas y ciencia de la computación por el que se pueden aplicar varias veces sin cambiar el resultado más allá de la aplicación inicial. El concepto de idempotencia surge en varios lugares del álgebra abstracta (en particular, en la teoría de proyectores y operadores de cierre ) y programación funcional (en la que está conectado a la propiedad de transparencia referencial ).

El término fue introducido por Benjamin Peirce en el contexto de elementos de álgebras que permanecen invariables cuando se elevan a un poder entero positivo, y literalmente significa "(la cualidad de tener) el mismo poder", de idem + potencia (mismo + poder).

Definición

Un elemento x de un conjunto S equipado con un operador binario • se dice que es idempotente bajo • si

xx = x .

La operación binaria • se dice que es idempotente si

xS , xx = x .

Ejemplos de

Funciones idempotentes

En el monoide ( E E , ∘) de las funciones de un conjunto E a sí mismo con composición de funciones ∘, los elementos idempotentes son las funciones f : EE tales que ff = f , es decir, que x , f ( f ( x )) = f ( x ) (la imagen de cada elemento en E es un punto fijo de f ). Por ejemplo:

Si el conjunto E tiene n elementos, podemos dividirlo en k puntos fijos elegidos y n - k puntos no fijos bajo f , y entonces k n - k es el número de funciones idempotentes diferentes. Por lo tanto, teniendo en cuenta todas las particiones posibles,

es el número total de posibles funciones idempotentes en el conjunto. La secuencia entera del número de funciones idempotentes dada por la suma anterior para n = 0, 1, 2, 3, 4, 5, 6, 7, 8, ... comienza con 1, 1, 3, 10, 41, 196 , 1057, 6322, 41393,… (secuencia A000248 en la OEIS ).

Ni la propiedad de ser idempotente ni la de no ser se conserva en la composición de funciones. Como ejemplo para el primero, f ( x ) = x mod 3 y g ( x ) = max ( x , 5) son ambos idempotentes, pero fg no lo es, aunque gf resulta serlo. Como ejemplo de este último, la función de negación ¬ en el dominio booleano no es idempotente, pero ¬ ∘ ¬ sí lo es. De manera similar, la negación unaria - () de números reales no es idempotente, pero - () ∘ - () sí lo es.

Significado de la informática

En informática , el término idempotencia puede tener un significado diferente según el contexto en el que se aplique:

Esta es una propiedad muy útil en muchas situaciones, ya que significa que una operación puede repetirse o reintentarse tantas veces como sea necesario sin causar efectos no deseados. Con operaciones no idempotentes, el algoritmo puede tener que realizar un seguimiento de si la operación ya se realizó o no.

Ejemplos de informática

Una función que busca el nombre y la dirección de un cliente en una base de datos suele ser idempotente, ya que esto no provocará que la base de datos cambie. De manera similar, una solicitud para cambiar la dirección de un cliente a XYZ suele ser idempotente, porque la dirección final será la misma sin importar cuántas veces se envíe la solicitud. Sin embargo, la solicitud de un cliente para realizar un pedido no suele ser idempotente, ya que varias solicitudes darán lugar a que se realicen varios pedidos. Una solicitud de cancelación de un pedido en particular es idempotente porque no importa cuántas solicitudes se realicen, el pedido permanece cancelado.

Sin embargo, una secuencia de subrutinas idempotentes donde al menos una subrutina es diferente de las otras, no es necesariamente idempotente si una subrutina posterior en la secuencia cambia un valor del que depende una subrutina anterior; la idempotencia no está cerrada bajo la composición secuencial . Por ejemplo, suponga que el valor inicial de una variable es 3 y hay una secuencia de subrutina que lee la variable, luego la cambia a 5 y luego la vuelve a leer. Cada paso de la secuencia es idempotente: ambos pasos que leen la variable no tienen efectos secundarios y el paso que cambia la variable a 5 siempre tendrá el mismo efecto sin importar cuántas veces se ejecute. No obstante, ejecutar la secuencia completa una vez produce la salida (3, 5), pero ejecutarla una segunda vez produce la salida (5, 5), por lo que la secuencia no es idempotente.

int x = 3;
void read() { printf("%d\n", x); }
void change() { x = 5; }
void sequence() { read(); change(); read(); }

int main() {
  sequence();  // prints "3\n5\n"
  sequence();  // prints "5\n5\n"
  return 0;
}

En el Protocolo de transferencia de hipertexto (HTTP), la idempotencia y la seguridad son los atributos principales que separan los métodos HTTP . De los principales métodos HTTP, GET, PUT y DELETE deben implementarse de manera idempotente de acuerdo con el estándar, pero POST no tiene por qué serlo. GET recupera el estado de un recurso; PUT actualiza el estado de un recurso; y DELETE elimina un recurso. Como en el ejemplo anterior, la lectura de datos no suele tener efectos secundarios, por lo que es idempotente (de hecho, nulipotente ). La actualización y la eliminación de un dato dado suelen ser idempotentes siempre que la solicitud identifique de forma única el recurso y solo ese recurso nuevamente en el futuro. PUT y DELETE con identificadores únicos se reducen al simple caso de asignación a una variable de un valor o el valor nulo, respectivamente, y son idempotentes por la misma razón; el resultado final es siempre el mismo que el resultado de la ejecución inicial, incluso si la respuesta es diferente.

La violación del requisito de identificación única en el almacenamiento o la eliminación generalmente causa una violación de la idempotencia. Por ejemplo, almacenar o eliminar un determinado conjunto de contenido sin especificar un identificador único: las solicitudes POST, que no necesitan ser idempotentes, a menudo no contienen identificadores únicos, por lo que la creación del identificador se delega al sistema receptor que luego crea un nuevo registro correspondiente. De manera similar, las solicitudes PUT y DELETE con criterios no específicos pueden generar resultados diferentes según el estado del sistema, por ejemplo, una solicitud para eliminar el registro más reciente. En cada caso, las ejecuciones posteriores modificarán aún más el estado del sistema, por lo que no son idempotentes.

En el procesamiento del flujo de eventos , la idempotencia se refiere a la capacidad de un sistema para producir el mismo resultado, incluso si el mismo archivo, evento o mensaje se recibe más de una vez.

En una arquitectura de almacenamiento de carga , las instrucciones que pueden causar un error de página son idempotentes. Entonces, si ocurre una falla de página, el sistema operativo puede cargar la página desde el disco y luego simplemente volver a ejecutar la instrucción fallada. En un procesador donde tales instrucciones no son idempotentes, lidiar con fallas de página es mucho más complejo.

Al reformatear la salida, se espera que la impresión bonita sea ​​idempotente. En otras palabras, si la salida ya es "bonita", no debería haber nada que hacer por la impresora bonita.

En la arquitectura orientada a servicios (SOA), un proceso de orquestación de varios pasos compuesto en su totalidad por pasos idempotentes se puede reproducir sin efectos secundarios si falla alguna parte de ese proceso.

Muchas operaciones que son idempotentes a menudo tienen formas de "reanudar" un proceso si se interrumpe, formas que terminan mucho más rápido que empezar desde el principio. Por ejemplo, reanudar una transferencia de archivos , sincronizar archivos , crear una compilación de software , instalar una aplicación y todas sus dependencias con un administrador de paquetes , etc.

Ejemplos aplicados

Un botón de paso de peatones típico es un ejemplo de un sistema idempotente

Los ejemplos aplicados que muchas personas podrían encontrar en su vida cotidiana incluyen botones de llamada de ascensor y botones de paso de peatones . La activación inicial del botón mueve el sistema a un estado de solicitud, hasta que se satisface la solicitud. Las activaciones posteriores del botón entre la activación inicial y la satisfacción de la solicitud no tienen ningún efecto, a menos que el sistema esté diseñado para ajustar el tiempo para satisfacer la solicitud en función del número de activaciones.

Ver también

Referencias

Otras lecturas