The counter was atomic and the pair was not

# Self-authored for the EML case corpus (no external origin). Every increment
# of the seat counter is atomic and no increment has ever been lost. How many
# seats were sold is computed below.
#
# The counter is correct. It is a hardware atomic, every increment is a single
# uninterruptible operation, and a stress test running sixteen workers for an
# hour ends with a count exactly equal to the number of increments issued. Not
# one is lost. Reading it is atomic too.
#
# The booking is not one operation. It reads the counter, compares it to the
# limit, and increments — three atomics, and nothing holds between them. Every
# step is indivisible and the sequence is not.
#
# Sixteen workers claim the last seats at once. Each reads a number below the
# limit, each is right about what it read, and each increments.

500 => seat_limit
2400 => claim_attempts
16 => workers
# Measured over the contended window: claims that passed the check and
# incremented.
523 => seats_granted
0 => increments_lost

seats_granted - seat_limit => seats_beyond_the_limit
claim_attempts - seats_granted => claims_correctly_refused

"seat limit               : " + str(seat_limit) ^0
"claim attempts           : " + str(claim_attempts) ^0
"concurrent workers       : " + str(workers) ^0
"seats granted            : " + str(seats_granted) ^0
"granted beyond the limit : " + str(seats_beyond_the_limit) ^0
"claims refused           : " + str(claims_correctly_refused) ^0
"" ^0

# ---- what atomicity verified ----

"the counter under the stress test" ^0
"  increments issued : " + str(claim_attempts) ^0
"  increments lost   : " + str(increments_lost) ^0
"  torn reads        : 0" ^0
"  final value equals the number issued : yes" ^0
"  verdict           : ATOMIC" ^0
"" ^0
"  every claim in this test is true, and the counter would" ^0
"  survive a far harsher one" ^0
"" ^0

# ---- what the booking does ----

"one booking, in operations" ^0
"  1. read the counter    : atomic" ^0
"  2. compare to the limit: on the value read in step 1" ^0
"  3. increment           : atomic" ^0
"  held across 1 to 3     : nothing" ^0
"" ^0
"  the limit is enforced against a value that was true when" ^0
"  it was read and need not be true when step 3 runs" ^0
"" ^0

int(seats_beyond_the_limit * 10000 / seat_limit) => overshoot_per_myriad
"overshoot against the limit : " + str(overshoot_per_myriad) + " per ten thousand" ^0
"" ^0

# ---- why it is bounded by the workers ----

# The overshoot cannot exceed the number of threads that can be between step 1
# and step 3 at once, which is why it looks small and why it is invisible at
# low concurrency and grows with the fleet.
"the size of the window" ^0
"  workers that can sit between read and increment : " + str(workers) ^0
"  overshoot observed                              : " + str(seats_beyond_the_limit) ^0
"  overshoot at one worker                         : 0" ^0
"" ^0
"  the bug is a function of the fleet size, so it arrives" ^0
"  when the service is scaled and not when it is written" ^0
"" ^0

# ---- null control ----

# The same atomic counter, claimed with a compare-and-swap loop so the check and
# the increment are one operation.
seat_limit => nc_seats_granted
0 => nc_seats_beyond_the_limit

"null control - compare-and-swap instead of read then add" ^0
"  increments lost          : " + str(increments_lost) + ", unchanged" ^0
"  seats granted            : " + str(nc_seats_granted) ^0
"  granted beyond the limit : " + str(nc_seats_beyond_the_limit) ^0
"  the counter did not become more atomic; the check and" ^0
"  the increment became one operation instead of two" ^0
"" ^0

# ---- the rule ----

"what an atomic counter guarantees" ^0
"  no increment is lost                 : exactly" ^0
"  a limit tested against it is honoured: not addressed;" ^0
"    atomicity is a property of one operation and a limit" ^0
"    is a relation between two" ^0
"" ^0
"composing atomics does not compose their atomicity; the" ^0
"question is never whether each step is indivisible but" ^0
"whether anything can change between them" ^0
"" ^0

"The counter is atomic and the stress test is right to say so: " + str(claim_attempts) + " increments" ^0
"issued, " + str(increments_lost) + " lost, 0 torn reads, final value exact. " + str(seats_granted) + " seats were granted" ^0
"against a limit of " + str(seat_limit) + " - " + str(seats_beyond_the_limit) + " beyond it, " + str(overshoot_per_myriad) + " per ten thousand - because" ^0
"the read, the comparison and the increment are three atomic operations with" ^0
"nothing held across them, and " + str(workers) + " workers can stand between the first and last." ^0

seat_limit = 500
claim_attempts = 2400
workers = 16
seats_granted = 523
increments_lost = 0
seats_beyond_the_limit = seats_granted - seat_limit
claims_correctly_refused = claim_attempts - seats_granted
print("seat limit               : " + str(seat_limit))
print("claim attempts           : " + str(claim_attempts))
print("concurrent workers       : " + str(workers))
print("seats granted            : " + str(seats_granted))
print("granted beyond the limit : " + str(seats_beyond_the_limit))
print("claims refused           : " + str(claims_correctly_refused))
print("")
print("the counter under the stress test")
print("  increments issued : " + str(claim_attempts))
print("  increments lost   : " + str(increments_lost))
print("  torn reads        : 0")
print("  final value equals the number issued : yes")
print("  verdict           : ATOMIC")
print("")
print("  every claim in this test is true, and the counter would")
print("  survive a far harsher one")
print("")
print("one booking, in operations")
print("  1. read the counter    : atomic")
print("  2. compare to the limit: on the value read in step 1")
print("  3. increment           : atomic")
print("  held across 1 to 3     : nothing")
print("")
print("  the limit is enforced against a value that was true when")
print("  it was read and need not be true when step 3 runs")
print("")
overshoot_per_myriad = int(seats_beyond_the_limit * 10000 / seat_limit)
print("overshoot against the limit : " + str(overshoot_per_myriad) + " per ten thousand")
print("")
print("the size of the window")
print("  workers that can sit between read and increment : " + str(workers))
print("  overshoot observed                              : " + str(seats_beyond_the_limit))
print("  overshoot at one worker                         : 0")
print("")
print("  the bug is a function of the fleet size, so it arrives")
print("  when the service is scaled and not when it is written")
print("")
nc_seats_granted = seat_limit
nc_seats_beyond_the_limit = 0
print("null control - compare-and-swap instead of read then add")
print("  increments lost          : " + str(increments_lost) + ", unchanged")
print("  seats granted            : " + str(nc_seats_granted))
print("  granted beyond the limit : " + str(nc_seats_beyond_the_limit))
print("  the counter did not become more atomic; the check and")
print("  the increment became one operation instead of two")
print("")
print("what an atomic counter guarantees")
print("  no increment is lost                 : exactly")
print("  a limit tested against it is honoured: not addressed;")
print("    atomicity is a property of one operation and a limit")
print("    is a relation between two")
print("")
print("composing atomics does not compose their atomicity; the")
print("question is never whether each step is indivisible but")
print("whether anything can change between them")
print("")
print("The counter is atomic and the stress test is right to say so: " + str(claim_attempts) + " increments")
print("issued, " + str(increments_lost) + " lost, 0 torn reads, final value exact. " + str(seats_granted) + " seats were granted")
print("against a limit of " + str(seat_limit) + " - " + str(seats_beyond_the_limit) + " beyond it, " + str(overshoot_per_myriad) + " per ten thousand - because")
print("the read, the comparison and the increment are three atomic operations with")
print("nothing held across them, and " + str(workers) + " workers can stand between the first and last.")

seat limit               : 500
claim attempts           : 2400
concurrent workers       : 16
seats granted            : 523
granted beyond the limit : 23
claims refused           : 1877

the counter under the stress test
  increments issued : 2400
  increments lost   : 0
  torn reads        : 0
  final value equals the number issued : yes
  verdict           : ATOMIC

  every claim in this test is true, and the counter would
  survive a far harsher one

one booking, in operations
  1. read the counter    : atomic
  2. compare to the limit: on the value read in step 1
  3. increment           : atomic
  held across 1 to 3     : nothing

  the limit is enforced against a value that was true when
  it was read and need not be true when step 3 runs

overshoot against the limit : 460 per ten thousand

the size of the window
  workers that can sit between read and increment : 16
  overshoot observed                              : 23
  overshoot at one worker                         : 0

  the bug is a function of the fleet size, so it arrives
  when the service is scaled and not when it is written

null control - compare-and-swap instead of read then add
  increments lost          : 0, unchanged
  seats granted            : 500
  granted beyond the limit : 0
  the counter did not become more atomic; the check and
  the increment became one operation instead of two

what an atomic counter guarantees
  no increment is lost                 : exactly
  a limit tested against it is honoured: not addressed;
    atomicity is a property of one operation and a limit
    is a relation between two

composing atomics does not compose their atomicity; the
question is never whether each step is indivisible but
whether anything can change between them

The counter is atomic and the stress test is right to say so: 2400 increments
issued, 0 lost, 0 torn reads, final value exact. 523 seats were granted
against a limit of 500 - 23 beyond it, 460 per ten thousand - because
the read, the comparison and the increment are three atomic operations with
nothing held across them, and 16 workers can stand between the first and last.

Trace event types