Events and news relevant to the Laboratory for Foundations of Computer Science

[Ohad Kammar <ohad.kammar@ed.ac.uk>]

Hi,

We'll have an LFCS seminar today:

  Tuesday, 30 Sep, 4.10pm

  Leslie Ann Goldberg, University of Oxford

  The seminar will take place in-person only.

We're synchronising the seminar time with the teaching timetable, and

plan to start the talk at the advertised time, so please arrive a minute or two

earlier.

In detail:

----------------------------------------------------------------------

Leslie Ann Goldberg, University of Oxford

https://www.cs.ox.ac.uk/people/leslieann.goldberg/

  Tue, 30 Sep, 4.10pm

  Venue: IF G.03

Title: Instability of Contention Resolution Protocols

Abstract

In contention resolution, multiple processors try to coordinate

sending discrete messages through a shared channel which supports

limited communication. If two processors send at the same time, the

messages collide and are not transmitted successfully. A

contention-resolution protocol is a randomised algorithm that the

processors use to decide when to send (and when to wait because the

channel is too busy). The most famous example is “binary exponential

backoff'' which underlies the Ethernet. Aldous proved in 1987 that

binary exponential backoff is not stable for any positive arrival

rate. He conjectured the same for any contention-resolution protocol

in a wide class of protocols called “acknowledgement-based

protocols''. I will give an update on the state of this conjecture.

(joint work with John Lapinskas)

----------------------------------------------------------------------

Upcoming seminars:

------------------

07 Oct: Zongchen Chen, Georgia Institute of Technology (Georgia Tech)

14 Oct: Bruno Cavalar, University of Oxford

21 Oct: Xinyuan Zhang, Nanjing University

28 Oct: Patrick Totzke, University of Liverpool: Optimally Controlling a Random

        Population

If you would like to propose a speaker, or speak yourself, please contact me.

The seminar webpages:

http://web.inf.ed.ac.uk/lfcs/events/lfcs-seminars

Yours,

Ohad.

The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. Is e buidheann carthannais a th’ ann an Oilthigh Dhùn Èideann, clàraichte an Alba, àireamh clàraidh SC005336.