Učitavanje video playera...
01:16:57
Filip Nikšić: Nasumično testiranje distribuiranih sustava
Sažetak: Mnoge pogreške u kompleksnim distribuiranim sustavima nastaju
interakcijom malog broja ključnih događaja. U nekim situacijama moguće
je testirati sve interakcije koje uključuju do k događaja, za malu
konstantu k, izvršavajući familiju testova čija je veličina
polinomijalna ili čak logaritamska u odnosu na veličinu sustava.
U predavanju predstavljamo dvije instance ovog fenomena. Prvo govorimo
zašto je u distribuiranom sustavu s n čvorova moguće pronaći mnoge
pogreške simuliranjem svega O(log n) nasumično odabranih mrežnih
particija. U drugom dijelu predstavljamo nasumičan algoritam za
pronalaženje pogrešaka uzrokovanih nizanjem malog broja događaja u
specifičnom redoslijedu. Algoritam dolazi s garancijom na vjerojatnost
pronalaska pogreške ukoliko ona postoji.
