BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20200329T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20201025T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260406T074318Z
UID:1600171200@ist.ac.at
DTSTART:20200915T140000
DTEND:20200915T150000
DESCRIPTION:Speaker: Rupak MAJUMDAR\nhosted by Tom HENZINGER\nAbstract: Ran
 dom testing has proven to be an effective way to catch bugs in concurrent 
 and distributedsystems. This is often surprising\, as the space of executi
 ons is enormous and conventional formalmethods intuition would suggest tha
 t bad behaviors would only be found by extremelyunlikely coincidences.Empi
 rically\, many bugs in distributed systems can be explained by interaction
 s amongonly a small number of features. Thus\, one can attempt to explain 
 the effectiveness ofrandom testing under various “small depth" hypothese
 s. In particular\, it may be possible totest all interactions of k feature
 s for a small constant k by executing a family of tests that isexponential
 ly or even doubly-exponentially smaller than the family of all tests. More
 over\,under certain conditions\, a randomly chosen small set of tests is s
 ufficient to cover all k-wiseinteractions with high probability.I will des
 cribe two concrete scenarios. First\, I will describe bugs in distributed 
 systemscaused by network partition faults. In many practical instances\, t
 hese bugs occur due to twoor three key nodes\, such as leaders or replicas
 \, not being able to communicate\, or becausethe leading node finds itself
  in a block of the partition without quorum. In this case\, I willshow usi
 ng the probabilistic method that a small set of randomly chosen tests will
  cover all“small partition” scenarios with high probability.Second\, I
  will consider bugs that arise due to unexpected schedules (interleavings)
  ofconcurrent events. Again\, many bugs depend only on the relative orderi
 ng of a small numberof events (the “bug depth” of the bug). In this ca
 se\, I will show a testing algorithm thatprioritizes low depth interleavin
 gs and a randomized testing algorithm that bounds theprobability of sampli
 ng any behavior of bug depth k for a fixed k. The testing algorithmis base
 d on combinatorial insights from the theory of partial orders\, such as th
 e notionof dimension and its generalization to d-hitting families as well 
 as results on online chainpartitioning.
LOCATION:https://istaustria.zoom.us/j/92615827655?pwd=OHk4TVV1bG9FcWVXSCsvN
 FQ3MmZrQT09 Meeting ID: 926 1582 7655 Passcode: 993438\, ISTA
ORGANIZER:
SUMMARY:Rupak MAJUMDAR: Random Testing of Distributed Systems with Theoreti
 cal Guarantees
URL:https://talks-calendar.ista.ac.at/events/2852
END:VEVENT
END:VCALENDAR