Seat Selection and Reservation: A Graph Problem Wearing an Airline Uniform

Seat selection looks like a grid of clickable squares. It is a graph with hard legality constraints, a finite shared inventory, and a reservation race that a seat map is uniquely bad at handling — because the entire map is on screen, to everyone, at the same time, updating in real time.

The scale

  a single narrow-body flight
    180 seats
      - 24 business (2-2, some 2-3-2)
      - 156 economy (3-3)
    a wide-body
      300-400 seats, multiple cabins
      (first, business, premium, economy)

    per flight, the system must handle
      - 300-400 concurrent viewers
      - a burst of seat selections in the
        last 10 minutes before departure
      - a burst of reselections (people
        changing their minds)
      - and the flight sells out

  the naive model
    seat: { id, row, letter, cabin,
            status: FREE | HELD | SOLD }

The graph and the legality constraints

  a seat map is a graph
    nodes = seats
    edges = adjacency (side-by-side,
            front/behind, aisle proximity)
    attributes:
      - cabin and zone
      - position: window / middle / aisle
      - row number
      - seat type: standard, extra
        legroom, recliner, bassinet
      - legroom, pitch, recline angle
      - restrictions: exit row, bulkhead,
        behind galley/lav, no
        recline, bassinet-only,
        stroller-tag-only

  hard legality rules (per aircraft type)
    - EXIT ROW: able-bodied adult,
      not with an infant, not
      unaccompanied minor, must be
      seated in specific rows, must
      have a specific seat letter,
      cannot be a bassinet position
    - BASSINET: allocated to a specific
      seat position per row, capacity
      limits, cannot be a seat that
      reclines
    - STROLLER / BULKHEAD: infant
      restraints, must be in front of
      or behind a bulkhead depending
      on the seat pitch
    - BEHIND GALLEY/LAVATORY: some
      airlines restrict; some do not,
      but the noise complaints are real
    - NO-RECLINE: a seat that must not
      recline because of a wall
      immediately behind
    - LIMITS: max 4 infants in a
      section, max 2 bassinets per
      section, no more than N URMs
      in a segregated area

  these are REGULATORY, not
  product-preference rules
  -> a violation is a safety and
     legal problem, not a UX annoyance

The hard part is that the legality rules are not expressible as a simple predicate on a seat. Exit row eligibility depends on the passengers on the flight (an adult, not an infant, not a URM) as well as the seat, and some limits are per-section counts (no more than four bassinets in a section, no more than N URMs in a segregated block). So seat validation is a query over the seat, the passenger, the booking, and the aggregate state of the cabin.

The pragmatic design is to precompute, per aircraft type, a set of seat attributes and a set of section-level rules, and to evaluate the seat-level predicate on the client for instant feedback while the server is authoritative. The count-based rules (bassinets, URM limits) are the ones that need a cabin-wide view, and they are usually handled as “if the section limit is full, the remaining bassinet seats show as unavailable” — computed on the server and pushed to the client as a seat-state hint.

The aircraft-type dependency is the source of most of the mess. Seat 22A on a 737 is an exit row; on an A320 it may be a normal row or not exist at all. Seat 15C on a 787 with a 3-4-3 layout is an aisle seat; on a 777-300ER with 3-4-3 it is a middle seat. So the seat map is keyed by (aircraft type, cabin layout version) and the booking has to be bound to the specific operating flight, not to the marketed flight number.

The reservation race

  the scenario
    seat 23C is FREE
    - passenger A has it in the map,
      highlighted, about to click
    - passenger B clicked two seconds ago
      and the request is in flight
    - passenger C is on the same seat
      from a different device

  the wrong implementations
    1. check-then-write
       both read FREE, both write SOLD
       -> double-sold seat
    2. client-side lock
       "disable the seat on click"
       -> protects one client, not two
    3. pessimistic seat lock
       hold the seat while the user
       confirms
       -> works, but 300 users
          refreshing an outbound flight
          with 180 seats is a lot of
          holds for a temporary state

  the right implementation
    a single atomic operation:
      UPDATE seat_inventory
      SET status = 'HELD', holder = <user>
      WHERE flight_id = ? AND seat_id = ?
        AND status = 'FREE'
    -> check the affected row count
    -> 1 = you got it, 0 = someone
       else did, return a clean
       "already taken" with a
       suggestion
    this is a compare-and-set
    (an optimistic concurrency
     primitive), and it is what the
    whole feature rests on

The compare-and-set is the correct primitive and it is worth being precise about why. A pessimistic hold (lock the seat for 90 seconds while the passenger completes) is defensible too, and it is what many systems do, but it means the seat is unavailable to everyone during the hold, which on a flight filling up means a passenger who is ready to select gets locked out by someone else’s abandoned form.

The compare-and-set version has no hold at all for a free seat selection in a low-stakes context: the click is the commitment, the server atomically claims, and the user gets immediate feedback. The “hold” concept is then reserved for the case where the selection is genuinely part of a checkout (a seat held while the passenger completes payment, or as part of an itinerary selection), where a hold is warranted because abandoning it wastes real work.

Whichever model is chosen, the client needs to handle the losing case gracefully, because losing the race is normal, not exceptional. “That seat was just taken — here are the nearest available seats in your preferred area” is the right response, and it requires the API to return alternatives, not just a failure code.

Holds, and the checkout connection

  a seat in a checkout flow
    1. passenger selects a seat
    2. the seat is HELD (e.g. 10 min)
       - counted against inventory
       - other passengers see it as
         taken
    3. passenger completes payment
    4. hold -> SOLD, attached to the PNR
    5. hold expires -> released

  the complexity is that a seat
  is not bought alone
    - it is part of an itinerary
    - several seats for one booking
    - the booking may fail after seats
      are held (payment, other segments)
    - so seats are held as a SET,
      and released as a set

  and the PNR (record locator) is the
  unit of truth for the airline
    - seat assignments live in the PNR
    - a change of flight changes the
      seat map and invalidates them

Seat selection in an airline is not a separate purchase; it is an attribute of a passenger on a flight, and the unit of truth is the PNR in the airline’s reservation system. That means the seat map system is a front end to a downstream system of record, and the “sold” state is really “this seat is assigned to this passenger in this PNR,” which is a fact that lives somewhere else. The architectural consequence is that seat state has two layers: a fast local projection for the map (what to show), and the authoritative PNR assignment (what is true). The projection must be reconciled against the PNR, and a failed PNR write means the local state is wrong and has to be rolled back — which is a distributed transaction with an external system, and the practical answer is a saga: reserve locally, write to the PNR, and on failure release locally and tell the user, with a retry worker for the in-between states.

The codeshare problem

  the scenario
    passenger books BA1234 LHR-JFK
    the operating carrier is AA
    (a codeshare)
    the seat map shown was the
    marketing carrier's layout
    the actual operating aircraft is
    a different type, or a different
    configuration

  what goes wrong
    - the "aisle seat" is a middle seat
    - the "legroom seat" does not exist
    - bassinet positions differ
    - the seat letter is wrong
    - exit row rules differ

  the mitigations
    - key the map to the OPERATING
      flight, resolved at booking
    - before departure, re-resolve and
      notify if the operating aircraft
      changed, with a free re-selection
    - allow free seat changes until
      check-in
    - and for multi-leg itineraries, a
      seat per leg

This is the single most common source of “I paid for an aisle seat and got a middle seat” and it is entirely a data problem: the map must be resolved against the operating aircraft, which can change up to the day of departure. A well-built system notifies the passenger when the operating aircraft changes and re-opens seat selection for free, because discovering it at the gate is the worst outcome and because the passenger paid for a specific seat attribute.

The multi-leg case matters too: a seat is per passenger per flight, and an itinerary with a connection has one seat on each leg. The UI has to make the “seat for this leg” distinction explicit rather than showing a single “select seats” step, because “I selected my seat” for a two-leg itinerary is a genuine ambiguity that generates a lot of support traffic.

Seat preference as a ranking

  the preference signal
    "aisle" "window" "front" "back"
    "near the lavatory" (exit row,
     usually, or they do not want it)
    "away from the galley" (or near,
     for those who want quick service)
    "together with family"
    "extra legroom"
    "bassinet if the baby is under 2"

  the ranking
    1. hard filters: legality, cabin
       class, availability
    2. soft preferences in the
       passenger's declared order
    3. "together" as a HARD constraint
       (adjacency, or a stated
        tolerance for being 1-2 rows
        apart)

  the adjacency case is a real
  optimisation
    - family of 4 wants 4 seats
      together
    - 2 window pairs, or 4 aisle,
      or 2+2 middle, or 1 window +
      1 aisle x2
    - and if the flight is nearly full,
      "together" often means none of
      the available 4-seat groups
      qualify -> the system should say
      "I can find 4 seats within 2 rows
       of each other" rather than fail

The family-adjacency case is a small combinatorial problem and worth building properly, because it is one of the highest-emotion moments in the whole product. A family of four on a full flight is exactly the case where the honest answer is “not together, but here is the best available” — and the system should be able to compute and say that rather than showing four grey seats.

Failure stories worth testing

Two users click the same seat within 100ms

Exactly one wins, the other gets a clean alternative suggestion. This is the compare-and-set test.

Let a user select an exit row with an infant

The server must reject it even if the client allowed the click. Client-side validation is UX, server-side is the safety requirement.

Fill the bassinet seats for a section and try to allocate a fifth bassinet

The section limit must be enforced with a cabin-wide view, not per-seat logic.

Change the operating aircraft on a codeshare two days before departure

The passenger must be notified and re-opened seat selection for free. This is the codeshare test.

Book a two-leg itinerary and select a seat

The seat assignment must be per leg and the UI must make that unambiguous.

Let an infant-in-seat booking take a seat with a non-reclining wall behind

No-recline seats must be filtered by passenger need, not just shown as “limited recline”.

Drop the PNR write after a local seat sale

The saga must release the local state and notify. An orphan hold is a revenue and trust problem.

Fill the flight to 95% and try to seat a family of four together

The system should return the best available configuration with a stated distance, not fail.

Reassign a passenger to a different seat during check-in

The map and the PNR must agree afterwards. Test the projection reconcile.

Two aircraft types with the same seat letter and different meaning (3-3 vs 3-4-3)

Confirm the map is keyed to the operating aircraft, not the flight number.

Let a user select a seat on a segment that later gets cancelled by the airline

The seat state must follow the segment, and the passenger must be re-seated with a notification.

A production-ready architecture

   flight + aircraft type resolution
        |
        v
  +----------------------------------------------------------+
  |  SEAT MAP GENERATOR (not an editor)                      |
  |  - from aircraft type + cabin layout + rules             |
  |  - precomputed: seat attributes, adjacency,             |
  |    section, restrictions, legroom                        |
  |  - exit-row / bassinet / bulkhead legality encoded here  |
  +----------------------------+-----------------------------+
                               |
                               v
  +----------------------------------------------------------+
  |  SEAT STATE PROJECTION                                    |
  |  - per flight: seat status, holder, cabin, restrictions  |
  |  - section-level limits (bassinets, URMs) as hints        |
  |  - reconciled against the PNR, not the source of truth   |
  +----------------------------+-----------------------------+
                               |
                               v
  +----------------------------------------------------------+
  |  RESERVATION                                              |
  |  - compare-and-set for a direct selection                |
  |  - hold with expiry when part of checkout                 |
  |  - set semantics for multi-seat family selection          |
  |  - PNR write in a saga with retry + rollback              |
  |  - alternatives computed on the losing path               |
  +----------------------------+-----------------------------+
                               |
                               v
  +----------------------------------------------------------+
  |  RANKING (preference, family adjacency, alternatives)   |
  |  - hard legality filters first                           |
  |  - declared preference order                             |
  |  - adjacency as an optimisation with a "best available"  |
  |    answer rather than a failure                           |
  +----------------------------+-----------------------------+
                               |
                               v
  +----------------------------------------------------------+
  |  RE-EVALUATION ON OPERATING-AIRCRAFT CHANGE              |
  |  - re-resolve the map, notify, re-open selection free    |
  +----------------------------+-----------------------------+

  watch: seat claim conflicts per 1000 selections, PNR
        reconciliation gaps, reseat notifications sent,
        adjacency satisfaction rate

Delivery checklist:

1. Generate the seat map from aircraft type, cabin layout, and rules rather than editing it. Legality constraints belong in the generator so every map is consistent.
2. Resolve the map to the operating flight, not the marketed flight number, and re-resolve with notification when the aircraft changes.
3. Use a single atomic compare-and-set for seat claims, and reserve holds for seats that are genuinely part of a checkout.
4. Handle the losing race well: return alternatives near the user’s preference, since losing a race is normal.
5. Enforce server-side legality against the passenger and the cabin, including section-level counts for bassinets and unaccompanied minors, not just per-seat attributes.
6. Model seat assignment as a per-passenger-per-flight attribute inside a PNR, with the local map as a projection, and write to the PNR in a saga with retry and rollback.
7. Make the seat step per leg on multi-leg itineraries, and label it clearly.
8. Build family adjacency as a real search, and return a “best available within N rows” answer rather than a failure.
9. Apply declared preferences as a ranking after hard legality filters, and let passengers re-open selection for free before check-in.
10. Reconcile the local projection against the PNR on a schedule, and alert on gaps.
11. Encode no-recline and accessibility needs as passenger-specific filters, not just map attributes.
12. Track seat-claim conflicts per thousand selections as the primary health metric for the race.

Common mistakes

Mistake	What actually happens	Better decision
Check-then-write on seat claim	Double-sold seats under load	Atomic compare-and-set
Client-side validation only	Unsafe or illegal seat gets sold	Server-side enforcement of legality
Editing the seat map directly	Maps become impossible over time	Generate from type, layout, rules
Keying the map to the flight number	Codeshare swaps the aircraft, wrong map	Resolve to the operating aircraft
Per-seat legality only	Bassinet and URM section limits breached	Cabin-wide section rules
One seat step for a two-leg trip	Ambiguity, support traffic	Seat per leg, labelled
Global seat lock for checkout	Everyone locked out by one abandonment	Hold only what is genuinely in checkout
No alternatives on the losing path	“Already taken” and no recovery	Return nearby preferred alternatives
Local seat state as source of truth	Drifts from the PNR	Projection + saga write + reconcile
Failure with no adjacency search	Family of four simply fails	Best-available-with-distance answer
No re-open on aircraft change	Passenger finds out at the gate	Notify and re-open selection free
Preferences applied before legality	Suggests seats they cannot have	Hard filters first
No conflict metric	Race problems found via complaints	Conflicts per 1000 selections
Assume a seat letter means the same thing	3-3 vs 3-4-3 aisle/middle mismatch	Key everything to the layout version

The complete story in one minute

A seat map is a graph wearing an airline uniform, and its constraints are regulatory rather than aesthetic: exit rows need an able-bodied adult and not an infant, bassinets are allocated to specific positions with per-section limits, bulkhead seats depend on the pitch, some seats must not recline, and unaccompanied minors have count limits in a segregated block. Those rules are not expressible as a predicate on a seat alone — several depend on who is on the flight and on cabin-wide counts — so the design is a generated map (from aircraft type, cabin layout, and rules, not hand-edited) with seat-level attributes precomputed and section-level limits pushed to the client as hints, enforced authoritatively on the server. Everything is keyed to the operating aircraft, not the marketed flight number, because seat 15C is an aisle seat in one layout and a middle seat in another, and a codeshare swap is the most common source of “I paid for an aisle and got a middle”.

The defining engineering problem is the reservation race, because the entire map is visible to everyone at once, updating live. It is a per-seat atomic compare-and-set — UPDATE ... WHERE status = 'FREE', checking the affected row count — not a check-then-write and not a global lock. A pessimistic hold for the whole map is wrong on a filling flight, since it lets one person’s abandoned form lock out everyone; reserve holds for seats genuinely part of a checkout, and let a direct selection be the commitment it actually is. Losing the race is normal, so the losing path must return alternatives near the passenger’s stated preference rather than a failure code.

Underneath it all, the unit of truth is the PNR in the airline’s reservation system, and the map is a fast projection of it — so a PNR write is a saga with retry and rollback, and the projection gets reconciled on a schedule. Multi-leg itineraries need a seat per leg, and family adjacency is a small search whose correct answer at 95% occupancy is “four seats within two rows” rather than an error.

generate the map from type/layout/rules; key to the operating aircraft
compare-and-set seat claims; holds only for checkout seats
legality on the server including cabin-wide section limits
PNR via saga, projection reconciled; per-leg seats; adjacency search

The hard part was never drawing the squares. It was that 400 people are looking at the same 180 squares and clicking at the same time, and the airline’s own record of who is sitting where lives in a system that does not know about the map at all.

What this team still owns

The seat map is a projection; the reservation/order system is authoritative. A hold needs a unique ID, passenger/segment scope, expiry, price snapshot, and conditional acquisition against the current seat version. Expiry releases local capacity, but reconciliation still has to handle a host confirmation that arrives after the hold looked expired. Never infer availability from map colour alone, and never let accessibility or exit-row eligibility exist only as client-side UI logic.

Technical references

• IATA: New Distribution Capability
• IATA: ONE Order
• FAA: emergency exit seating requirements, 14 CFR 121.585