logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro