Utilità del numero di consenso

Question

Quali informazioni e utilità conoscono il numero di consenso di un oggetto condiviso dammi?

Answer 1

Probabilmente non puoi fare molto meglio che citare l'abstract di La carta originale di Herlihy :

.

Un'attrementazione senza attesa di un oggetto dati concorrente è uno che garantisce che qualsiasi processo può completare qualsiasi operazione in un numero finito di passaggi, indipendentemente dalle velocità di esecuzione degli altri processi. Il problema di costruire un'implementazione senza attesa di un oggetto dati da un altro bugie nel cuore di un lavoro molto recente in algoritmi concomitanti, strutture di dati concorrenti e architetture multiprocessore. In primo luogo, introduciamo una tecnica semplice e generale, basata sulla riduzione di un protocollo di consenso, per dimostrare dichiarazioni del modulo, “ non vi è alcuna implementazione senza attesa di x da Y. " Derivamo una gerarchia di oggetti tali che nessun oggetto ad un unico livello ha un'implementazione senza attesa in termini di oggetti a livelli inferiori. In particolare, mostriamo che i registri di lettura / scrittura atomici, che sono stati al focus di molta recente attenzione, sono in fondo alla gerarchia: non possono essere utilizzati per costruire implementazioni senza attesa di molti tipi di dati semplici e familiari. Inoltre, primitivi di sincronizzazione classica come test e set e recupero e aggiungere, mentre più potenti della lettura e della scrittura, sono anche computazionalmente deboli, come sono i primitivi standard del passaggio del messaggio. Secondo, tuttavia, mostriamo che esistono semplici oggetti universali da cui si può costruire un'implementazione senza attesa di qualsiasi oggetto sequenziale.