ized or decentralized. For example, one participant said, “We could mark the same seat map with different colored markers for each sell.” [ID106] This participant’s solution is decentralized, since one can imagine individual sellers, each with their own colored marker, racing to mark off seats on a large map.

Another said, “This problem [of selling the same seat twice] could be avoided by allowing only one vendor at a time into the concert hall. But this would be unreasonable if the hall were too large or too many vendors were working to reserve seats. Perhaps if each vendor were responsible for a section of the hall, finding the best seats within their section, this problem would be solved.” [ID303] This response provides two solutions that eliminate potential conflicts, the first by enforcing exclusive access between the selection and the marking of seats, the other by dividing the resource (seats). Here, we could imagine sellers with cellphones dashing around the hall, placing markers on actual, physical seats. Note that scaling issues are mentioned in the proposed solution.

Common errors. The two most com-
mon errors in the student-proposed
solutions were in thinking that a
problem could be solved with a fast-
er system and in devising solutions
that simply moved concurrency to
another point in the algorithm. As
noted when we described decentral-
ized solutions, the surveyed students
suggested speed was necessary to
avoid many problems. For example,
one said, “To avoid this problem we
could have very high ‘refresh’ rates
or have a way of reserving n seats, as
the process is still going through.” [ID
423] Another said, “As soon as n seats
are marked unavailable, even before
payment processing, the seats need
to be marked unavailable. This way,
another seller cannot try to reserve a
seat that is already ‘reserved.’ …the
system (and screen) would need to be
refreshed every time a reservation is
made.” [ID 425]
Many proposed solutions moved
the point of concurrency. In one, it
was moved to a preview step, with
the participant saying, “One more
solution would be to have the com-

of the 66 students,
64 identified our
main problem of
interest—that it
may be possible
to sell a given seat
to more than one
person—good
evidence that even
novice computing
students are able to
identify this critical
concurrency issue.

puter show the n seats as unavailable
as soon as any seller has them up on
their screens. With this system, only
one seller could see these seats as
available at a time. If one seller (A)
pulls up n seats for a customer, then
another seller (B) searches for the
best seats, and the seats seller A was
looking at would not be shown to sell-
er B.” [ID122]
Another retargeting of the point of
concurrency was to a graphical inter-
face, with another saying, “Creating
a visual representation of the concert
hall through a computer would allevi-
ate this problem. Sellers would mark
a certain number of seats for their cli-
ents, letting other sellers know which
seats are purchased (potentially) and
which seats are free for booking.”
[ID413]
Another realized his/her distrib-
uted, graphical interface only hid the
concurrency problem, so proposed a
novel solution that apparently used
the inherent randomness of human
interaction to deal with the problem
of multiple sellers claiming the same
seats at the same time, saying, “Sell-
ers would each have their own com-
puters, and all of them would be con-
nected, so once a seat is claimed, all
other sellers would see it. If two sell-
ers happen to click at the same time, a
separate window opens, and both will
have to try again.” [ID402]
One interpretation of this solution
is that a separate window would open
when the computer detects a conflict
and forces the sellers to back off and
retry, assuming it unlikely that the
sellers would try again at precisely
the same moment. However, this idea
leaves many concurrency issues un-
resolved, including how the conflict
is detected and whether or not other
sellers could still get in and reserve
the seat(s) targeted by the two original
sellers.

Discussion

The proposed solutions of beginner students provide evidence of CS problem-solving skills through their ability to identify the problem and suggest reasonable, though relatively unsophisticated, solutions. By replicating the Ben-David Kolikant study, our study provided additional perspective in both analysis and results.