Ticket Dispenser algorithm and the size of the Ticket array

Question

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..

Answer 1

In the paper, it says:

Specification 1.

• a) The domain of tickets is the set of integers modulo mN for some integer m ≥ 3.
• b) At any time, the set of tickets that are active is confined to some interval of fewer than mN/2 consecutive integers modulo mN.

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$.