tickets sent to will call for the same
seats.” [ID412]
Citing concurrency, other students
expressed concern about dealing with
group sales, with one saying, “First of
all, there could be an issue of finding
group seating. Finding n best avail-
able seats will not necessarily do, if
they have to be n best available seats
together. In such a situation, each
seat should be labeled with how many
seats are available in front, behind,
and to the left and right of it.” [ID425]
Another said, “Scalpers and other
ticket-selling agencies will buy tickets
and sell them at an increased price;
with no limit on n, the number of tick-
ets the caller is purchasing, a single
caller could buy every ticket to the
concert. This problem is easily fixed
by putting an upper limit on n of eight
to 12 tickets; large groups can call a
special hotline and speak to an opera-
tor to purchase more.” [ID430]
The notion of “best seat” attract-
ed further attention, with one par-
ticipant handling the double-selling
problem by dividing the seats among
sellers. Most algorithmic attention
was then focused on the following
problem, as the participant described
it: “First of all, there would no longer
be a first-come-first-serve basis, and
problems would arise over who actu-
ally occupies the good seats first. If
it’s only one seller, she would be able
to take one customer at a time. Two or
more sellers would make it hard to de-
cide which seller’s customer actually
received the seats first.” [ID431]

Identifying the main synchronization
problem. The degree to which study
participants were able to identify the
problem varied, with most giving a
fairly standard “Sellers could mark
the seats unavailable at the same
time.” [ID412] or “There could be
double-booking.” [ID106] Saying this
scenario is unlikely was not uncom-
mon, with some participants identi-
fying computers or technology as the
source of the problem. For example,
one said, “One computer may be op-
erating slower than another, causing
the seats one seller saw to be taken by
another seller.” [ID406]
Others might not have addressed
technology specifically but did iden-
tify the key concept of time, with one
saying, “One major issue is when, and
how long, it takes to mark a seat as un-
available.” [ID410]
A few others gave more detailed
problem descriptions that hinted at
the kind of analysis that will eventual-
ly be needed to construct a genuinely
effective solution, including recogni-
tion of the interleaving problem. For
example, one said, “The first, most
obvious problem is overlap. If all sell-
ers are working at the same time, then
the system might display to Seller A
that certain seats are open, when, in
fact, they have already been reserved
by Seller B. Thus A will have to find
different seats, which might have, in
the intervening time, been reserved
by Seller C.” [ID 417]

cited earlier, concerning automatic
customer ordering, was that they be
“fast.” Some were less specific but
still involved implicit communica-
tion. For example, one participant
said, “The program would have to
temporarily mark seats being looked
at during a transaction as unavailable
so vendors couldn’t sell seats simulta-
neously.” [ID313]
Others were more specific, im-
posing additional restrictions while
prompting doubt as to the partici-
pant’s true understanding of concur-
rency. In one case, we saw evidence
of an attempt to move the potential
point of concurrent access in an ex-
pressed solution. “The only real way
to avoid this and still have multiple
sellers is to run the booking on a
computer network with a master list
of available seats. The process would
then go something like this: A caller
requests n seats. The master list can
be ordered in such a way that it fills the
seats front to back, left to right; when
a seller requests n seats, it gives the
next n seats on the list. Cancelled seat
orders are inserted at the top of the
available list, in order of precedence.
The seller can reserve the seats, ask
if they are acceptable to the custom-
er, and, if they are, proceed with the
transaction. This would avoid double-
booking, because during the time the
seller offers the seats to the customer,
they are withheld from the list, and
the other sellers drawing from the list
would not have access to those seats.”
[ID130]
C2 solutions differed from C1 in
their use of explicit communication
with a centralized resource making
seat assignments, sometimes iden-
tified as a database. The quote from
ID440 earlier on explicit ordering is
an example of this explicit communi-
cation.

Another variant of explicit communication involved a particular ordering required to ensure a safe process, including lockstepping and pipelining. For example, one participant said, “These problems [multiple bookings] might be avoided if instead of multiple people selling tickets and being involved in every step of the process, the selling process was divided between two employees. This way, while the second employee was