Sincronización multiproceso en programas concurrentes: selección completamente k-justa de interacciones

Abstract

La selección complemente justa surge en el contexto de los programas no deterministas y sirve para garantizar que todos los elementos que se habilitan infinitamente a menudo se seleccionan infinitamente a menudo. Esta noción de selección presenta dos anomalías: la finitud justa y las conspiraciones. Este artículo se centra en la selección justa de interacciones y presenta una nueva noción llamada selección completamente k justa cuya principal ventaja sobre otras propuestas es que da solución a las dos anomalías de forma simultánea y que le valor de k se puede establecer a priori para caracterizar su bondad. Para ello, hemos descrito un modelo abstracto de interacción que hace independiente el criterio de selección del lenguaje de programación y que se puede acomodar a una gran variedad de modelos de interacción. También presentamos un algoritmo general para implementar la selección completamente k justa de interacciones que no requiere acceder al estado local de los procesos del sistema.