Ponencia
An Algorithm for Ensuring Fairness and Liveness in Non-deterministic Systems Based on Multiparty Interactions
Autor/es | Ruiz Cortés, David
Corchuelo Gil, Rafael Pérez Castellanos, José Antonio Toro Bonilla, Miguel |
Departamento | Universidad de Sevilla. Departamento de Lenguajes y Sistemas Informáticos |
Fecha de publicación | 2002 |
Fecha de depósito | 2017-10-11 |
Publicado en |
|
ISBN/ISSN | 978-3-540-44049-9 0302-9743 |
Resumen | Strong fairness is a notion we can use to ensure that an element
that is enabled infinitely often in a non–deterministic programme,
will eventually be selected for execution so that it can progress. Unfortunately,
“eventually” ... Strong fairness is a notion we can use to ensure that an element that is enabled infinitely often in a non–deterministic programme, will eventually be selected for execution so that it can progress. Unfortunately, “eventually” is too weak to induce the intuitive idea of liveliness and leads to anomalies that are not desirable, namely fair finiteness and conspiracies. In this paper, we focus on non–deterministic programmes based on multiparty interactions and we present a new criteria for selecting interactions called strong k–fairness that improves on other proposals in that it addresses both anomalies simultaneously, and k may be set a priori to control its goodness. We also show our notion is feasible, and present an algorithm for scheduling interactions in a strongly k–fair manner using a theoretical framework to support the multiparty interaction model. Our algorithm does not require to transform the source code to the processes that compose the system; furthermore, it can deal with both terminating and non–terminating processes. |
Agencias financiadoras | Comisión Interministerial de Ciencia y Tecnología (CICYT). España |
Identificador del proyecto | TIC 2000–1106–C02–01 |
Cita | Ruiz Cortés, D., Corchuelo Gil, R., Pérez Castellanos, J.A. y Toro Bonilla, M. (2002). An Algorithm for Ensuring Fairness and Liveness in Non-deterministic Systems Based on Multiparty Interactions. En Euro-Par 2002: 8th International Euro-Par Parallel Processing Conference (563-572), Paderborn, Germany: Springer. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
An Algorithm for Ensuring.pdf | 249.3Kb | [PDF] | Ver/ | |