Un carácter topológico para la complejidad asincrónica resiliente arbitraria
Autores: Yue, Yunguang; Liu, Xingwu; Lei, Fengchun; Wu, Jie
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Un carácter topológico para la complejidad asincrónica resiliente arbitraria
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Ampliar
Marco basado en topología
Cuantificación
Clasificación
Complejidad asincrónica resiliente
Estructuras topológicas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 26
Citaciones: Sin citaciones
En este trabajo, ampliamos el marco y el método basados en la topología para la cuantificación y clasificación de la complejidad asincrónica general resiliente. Presentamos el , aplicado a tareas de decisión en un modelo de retraso iterado que se basa en una serie de objetos comunicantes, cada uno de los cuales consiste principalmente en el algoritmo de retraso. Para hacer esto, primero introducimos dos estructuras topológicas, complejo retardado y complejo retardado reducido, y construimos el modelo de computabilidad topológica, y luego investigamos algunas propiedades de esas estructuras y el poder computacional de ese modelo. Nuestro teorema establece que la complejidad temporal de cualquier algoritmo asincrónico resiliente arbitrario es proporcional al nivel de un complejo retardado reducido necesario para permitir un mapa simplicial desde el complejo de entrada de una tarea hasta su complejo de salida. Como aplicación, lo usamos para derivar los límites en la complejidad temporal para aproximar el acuerdo con procesos.
Descripción
En este trabajo, ampliamos el marco y el método basados en la topología para la cuantificación y clasificación de la complejidad asincrónica general resiliente. Presentamos el , aplicado a tareas de decisión en un modelo de retraso iterado que se basa en una serie de objetos comunicantes, cada uno de los cuales consiste principalmente en el algoritmo de retraso. Para hacer esto, primero introducimos dos estructuras topológicas, complejo retardado y complejo retardado reducido, y construimos el modelo de computabilidad topológica, y luego investigamos algunas propiedades de esas estructuras y el poder computacional de ese modelo. Nuestro teorema establece que la complejidad temporal de cualquier algoritmo asincrónico resiliente arbitrario es proporcional al nivel de un complejo retardado reducido necesario para permitir un mapa simplicial desde el complejo de entrada de una tarea hasta su complejo de salida. Como aplicación, lo usamos para derivar los límites en la complejidad temporal para aproximar el acuerdo con procesos.