you're reading...

SACT Seminar: Point and interval contention

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.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: