Time: 2:00pm Tuesday, 26th May.
Location: SIT 459
Speaker: Joel Gibson, University of Sydney
Title: Point and interval contention
Lock-free concurrent data structures are often analysed by giving an amortised running time bound per operation, involving some measure of contention: how many other operations are going on at the time. Two common measures of contention are the point contention, the maximum number of processes active at any one time during an operation, and the interval contention, the number of operations concurrent with a given operation.
Using properties of interval graphs, I show that these two measures are equivalent in an amortised context, by showing that when summed up across every operation the interval contention is at most twice the point contention. Furthermore, I show this bound is tight.