Geek Thoughts: no-fly lists and CAP Theorem

According to this article, a recent terror suspect almost got on a plane despite being recently added to the no-fly list. Why is it so difficult to administer a no-fly list? The CAP Theorem has answers. (Disclaimer: as always, this blog is apolitical–this isn’t about whether no-fly lists are a good idea or not, only a matter of technical interest)

Without stretching the imagination too much, one can think of a no-fly list as a distributed database. The list apparently changes frequently, and it needs to be accessible from thousands of airport gates and reservation desks. Thus CAP Theorem applies. In a nutshell, that theorem states that of Consistency, Availability, and Partition-tolerance, you can only pick, at most, two. Hit the link above for a much better, more complete description.

If there was one centralized list, the system would be Consistent and Available, but every time a name needed to be checked it would require an immediate network round-trip–should the connection to that central list go down, no further checks would be possible–no Partition tolerance.

Of course, the airline could set a policy that if said network connection goes down, no passengers at all would be able to get on planes. This would be a case of lack of Availability.

Or, the complete list could be periodically copied to each location that needs it. This provides good Availability and Partition tolerance, but fails Consistency, since it’s possible to miss out on late-breaking updates. Apparently, something like this is what happened.

More collected Geek Thoughts at http://geekthoughts.info.

Comments are closed.

MicahLogic is Stephen Fry proof thanks to caching by WP Super Cache