En vänta-fri hierarki kartlägger objekttyper till nivåer i {1, 2, 3,...} U {co}, och har följande egenskap: om en typ 2' är på nivå N, då, för alla typer T', det finns en vänta-fri implementation av ett objekt av typ T', för N-processer, använder endast register och objekt av typ T. Den oändliga hierarki som definieras av Herlihy är ett exempel på en vänta-fri hierarki. En vänta-fri hierarki är att byst om det har följande egenskap: om en t ype T är på nivå N, och S är en ändlig uppsättning typer som hör till nivåer N -1 eller lägre, då finns det ingen vänta-fri implementation av ett objekt av typ T, för N-processer, med vilket antal och varje kombination av objekt som hör till typerna i S. Robustness innebär att det inte finns några smarta sätt att kombinera svaga delade objekt för att få starkare. Tvärtemot vad många forskare tror bevisar vi att Herlihys hierarki inte är robust. Vi definierar sedan några naturliga varianter av Herlihys hierarki, som också är oändliga vänta-fria hierarkier. Med undantag för en, som fortfarande är öppen, är dessa inte heller robusta. Vi avslutar med den öppna frågan om det finns en icke-trivial robust vänta-fri hierarki.
Jayanti REF definierade en hierarkis robusthet som egenskapen att ett objekt på en högre nivå i hierarkin inte kan implementeras med hjälp av något antal eller en kombination av objekt lägre i hierarkin.
On the robustness of Herlihy's hierarchy
{'venue': "PODC '93", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}