Slumpmässiga tester har visat sig vara ett effektivt sätt att fånga fel i distribuerade system i närvaro av fel i nätverkspartitionen. Detta är förvånande, eftersom utrymmet för potentiellt felaktiga avrättningar är enorm, och buggarna är beroende av ett subtilt samspel mellan sekvenser av operationer och fel. Vi ger en teoretisk motivering av effektiviteten av slumpmässiga tester i detta sammanhang. För det första visar vi en allmän konstruktion, med hjälp av den probabilistiska metoden från kombinatorik, som visar att när ett slumpmässigt test täcker ett fast täckningsmål med tillräckligt hög sannolikhet, en liten slumpmässigt utvalda uppsättning tester uppnår full täckning med hög sannolikhet. I synnerhet visar vi att vår konstruktion kan ge provuppsättningar exponentiellt mindre än systematisk uppräkning. För det andra, baserat på en empirisk studie av många fel som upptäcks genom slumpmässiga tester i produktionsfördelade system, introducerar vi begrepp om testtäckning avseende fel på nätverkspartitioner som är effektiva när det gäller att hitta fel. Slutligen visar vi med hjälp av kombinatoriska argument att för dessa begrepp av testtäckning vi introducerar, kan vi hitta en lägre gräns på sannolikheten för att ett slumpmässigt test täcker ett givet mål. Vår allmänna konstruktion förklarar sedan varför slumpmässiga testverktyg uppnår bra täckning — och därmed, hitta buggar — snabbt. Medan vi formulerar våra resultat i termer av fel på nätverkspartitioner, ger vår konstruktion ett steg mot en strikt analys av slumpmässiga testalgoritmer, och kan tillämpas i andra scenarier.
Majumdar & Niksic argumenterade probabilistiskt för effektiviteten i denna randomiserade testmetod REF, vilket hjälper till att förklara varför vår teknik hittar buggar.
Why is random testing effective for partition tolerance bugs?
{'venue': 'PACMPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}