Abstrakt. Algoritmer för dynamisk partiell orderreduktion (DPOR) används vid statslös modellkontroll (SMC) för att bekämpa den kombinatoriska explosionen av antalet schemaläggningar som behöver undersökas för att garantera sundhet. Den mest effektiva av dem, den optimala DPOR algoritmen, är optimal i den meningen att den utforskar endast en schemaläggning per Mazurkiewicz spår. I detta dokument förstärker vi DPOR med begreppet observerbarhet, vilket gör att beroenden mellan operationer är beroende av förekomsten av framtida operationer, kallade observatörer. Observatörer leder naturligtvis till en lat konstruktion av beroenden. Detta kräver betydande förändringar i kärnan av POR algoritmer (och Optimal DPOR i synnerhet), men också gör den resulterande algoritmen, Optimal DPOR med Observatörer, super-optimal i den meningen att den utforskar exponentiellt mindre schemaläggningar än Mazurkiewicz spår i vissa fall. Vi hävdar att observatörer kommer naturligt i många konvergensmodeller, och visar de prestandafördelar som Optimal DPOR med Observatörer uppnår i både ett SMC-verktyg för delad minneskonvergens och ett verktyg för konvergens via meddelande passerar, med både syntetiska och faktiska program som riktmärken.
När det gäller DCDPOR utökar REF optimal DPOR med observatörer.
Optimal dynamic partial order reduction with observers
{'venue': 'TACAS', 'journal': None, 'mag_field_of_study': ['Computer Science']}