Reunión asíncrona en un anillo peligroso
Autores: Dobrev, Stefan; Flocchini, Paola; Prencipe, Giuseppe; Santoro, Nicola
Idioma: Inglés
Editor: MDPI
Año: 2023
Acceso abierto
Artículo científico
2023
Reunión asíncrona en un anillo peligroso
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Agentes
Anillo
Agujero negro
Reunión
Condiciones
Algoritmos
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 36
Citaciones: Sin citaciones
Consideremos un conjunto de agentes móviles asíncronos idénticos ubicados en un anillo anónimo de nodos. El problema clásico requiere que todos los agentes se encuentren en el mismo nodo, no decidido de antemano, dentro de una cantidad finita de tiempo. Este problema se ha estudiado asumiendo que la red es segura para los agentes. En este documento, consideramos la presencia en el anillo de un proceso estacionario ubicado en un nodo que deshabilita a cualquier agente entrante sin dejar rastro. Este nodo peligroso es conocido en la literatura como un agujero negro, y la determinación de su ubicación ha sido investigada extensamente. La presencia del agujero negro hace que sea determinísticamente inviable que todos los agentes se reúnan. Por lo tanto, la preocupación de la investigación es determinar cuántos agentes pueden reunirse y bajo qué condiciones. En este documento establecemos una caracterización completa de las condiciones bajo las cuales el problema puede resolverse. En particular, determinamos el número máximo de agentes que se pueden garantizar que se reúnan en el mismo lugar dependiendo de si es desconocido (al menos uno debe ser conocido). Estos resultados son ajustados: en cada caso, reunirse con un agente más es determinísticamente inviable. Todas nuestras pruebas de posibilidad son constructivas: proporcionamos algoritmos de agentes móviles que permiten a los agentes reunirse dentro de una distancia predefinida bajo las condiciones especificadas. El análisis de los costos de tiempo de estos algoritmos muestra que son óptimos. Nuestro algoritmo de reunión para el caso de desconocido también es una solución para el problema de ubicación del agujero negro. Interesantemente, su complejidad de tiempo limitado es; esto es una mejora significativa sobre la complejidad de tiempo limitado existente.
Descripción
Consideremos un conjunto de agentes móviles asíncronos idénticos ubicados en un anillo anónimo de nodos. El problema clásico requiere que todos los agentes se encuentren en el mismo nodo, no decidido de antemano, dentro de una cantidad finita de tiempo. Este problema se ha estudiado asumiendo que la red es segura para los agentes. En este documento, consideramos la presencia en el anillo de un proceso estacionario ubicado en un nodo que deshabilita a cualquier agente entrante sin dejar rastro. Este nodo peligroso es conocido en la literatura como un agujero negro, y la determinación de su ubicación ha sido investigada extensamente. La presencia del agujero negro hace que sea determinísticamente inviable que todos los agentes se reúnan. Por lo tanto, la preocupación de la investigación es determinar cuántos agentes pueden reunirse y bajo qué condiciones. En este documento establecemos una caracterización completa de las condiciones bajo las cuales el problema puede resolverse. En particular, determinamos el número máximo de agentes que se pueden garantizar que se reúnan en el mismo lugar dependiendo de si es desconocido (al menos uno debe ser conocido). Estos resultados son ajustados: en cada caso, reunirse con un agente más es determinísticamente inviable. Todas nuestras pruebas de posibilidad son constructivas: proporcionamos algoritmos de agentes móviles que permiten a los agentes reunirse dentro de una distancia predefinida bajo las condiciones especificadas. El análisis de los costos de tiempo de estos algoritmos muestra que son óptimos. Nuestro algoritmo de reunión para el caso de desconocido también es una solución para el problema de ubicación del agujero negro. Interesantemente, su complejidad de tiempo limitado es; esto es una mejora significativa sobre la complejidad de tiempo limitado existente.