# Ticket Dispenser algorithm and the size of the Ticket array

The following is a ticket Dispenser Mechanism, it's from the article:

"Closing the Complexity Gap between FCFS Mutual Exclusion and Mutual Exclusion By Robert Danek and Wojciech Golab" http://www.cs.toronto.edu/~rdanek/fcfs_disc.pdf

shared variables:

Tickets: array[0..7N-1] of {INUSE, FREE } initially Tickets[0..(3N-1)] = FREE

and Tickets[3N..(7N-1)] = INUSE

lastTicket: 0..7N-1 initially 7N-1

private variables: ticket: 0..7N-1 uninitialized


Implementation of ObtainTicket():

45 first := lastTicket 46 i := 1 // Find upper bound on the smallest FREE ticket.

47 while i < 3N ( Tickets[(first + i) mod 7N] = INUSE do

48   i := min {3N, i x 2 } // Now do binary search to find the ticket.

49 last := first + i 50 while first < last do

51 midpoint := RoundDown[(first + last )/2]

52 if Tickets[midpoint mod 7N] = INUSE then

53 first := midpoint + 1

54 else

55 last := midpoint // At this point first = last holds.

56 ticket := first mod 7N

57 Tickets[ticket ] := INUSE

58 return ticket

Implementation of DoneWithTicket(): // Reset a ticket that was previously active.

59 Tickets[(ticket + 3N) mod 7N] := FREE

60 lastTicket := ticket


Why do we need 7N tickets and not 3N ?, it seems to suffice if every process can run this function and bypass us up to 3 times while process p is inside (It's Guaranteed according to the paper)

The 7N size is not explained in the paper whatsoever..

According to their specification, the active tickets should be less than half the domain size. So if there are 3N active tickets, the next available integer $$m$$ that will ensure $$3N$$ is less than half of $$mN$$ is $$m=7$$.