A Message-Passing and Adaptive Implementation of the Randomized Test-and-Set ObjectReport as inadecuate




A Message-Passing and Adaptive Implementation of the Randomized Test-and-Set Object - Download this document for free, or read online. Document in PDF available to download.

* Corresponding author 1 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition CentraleSupélec, Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE 2 IRMAR - Institut de Recherche Mathématique de Rennes 3 IPSO - Invariant Preserving SOlvers IRMAR - Institut de Recherche Mathématique de Rennes, Inria Rennes – Bretagne Atlantique 4 LINA 5 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS Inria Rennes – Bretagne Atlantique , IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES

Abstract : —This paper presents a solution to the well-known Test-and-Set operation in asynchronous systems prone to process crashes. Test-and-Set is a synchronization operation that, when invoked by a set of processes, returns - yes - to a unique process and returns - no - to all the others. Recently many advances in implementing Test and Set objects have been achieved, however all of them uniquely target the shared memory model. In this paper we propose an implementation of a Test-and-Set object for message passing distributed systems. This implementation can be invoked by any number p of processes. It has an expected step complexity in Op and an expected message complexity in Onp, where n is the total number of processes in the system. The proposed Test and Set object is built atop a new basic building block that allows to select a winning group among two groups of processes.

Keywords : randomized algorithm crash failures -Test&Set synchronization asynchronous message-passing system





Author: Emmanuelle Anceaume - François Castella - Achour Mostefaoui - Bruno Sericola -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents