Complementarities in markets and computers

One thing that makes it difficult for markets to clear efficiently is if goods are complements, so that you only want good A if you can also have good B (e.g. you need two licences of adjacent-frequency radio spectrum to carry out your broadband business plan, or you are willing to take job A only if your spouse can get an appropriate job in the same city). If the market isn't designed to take this into account, there might be coordination failures, in which some buyer ends up having paid good money but having gotten only part of what he needs, or in which you and your spouse end up with jobs in different cities. Combinatorial auctions, and labor clearinghouses that accomodate couples, are market designs that seek to avoid these kinds of coordination failures.

The same kind of thing can cause your computer to freeze. If program A needs parts X and Y of your computer memory, and so does program B, and they each lock up one of those components while they try to call the other, you may have to send the children out of the room and reboot. The programming solutions for avoiding this can involve some sort of clearinghouse. Here's an article on the subject from Dr. Dobb's Journal: Lock Options, A compile-time deadlock prevention scheme.

The introduction begins:
"The two major problems in concurrent programs are data races and deadlocks. Races occur when two or more threads are accessing shared memory without proper synchronization. Deadlocks occur when synchronization is based on locking and multiple threads block each other's progress. In a typical deadlock scenario, thread A locks the mutex X, and thread B locks the mutex Y. Now, in lockstep, thread A tries to lock Y and B tries to lock X. Neither can make progress, waiting forever for the other thread to release its lock. The program freezes.
In a sense, data races are the opposite of deadlocks. The former result from not enough synchronization, the latter usually happen when there's too much synchronization and it gets out of hand.
There are sophisticated schemes to prevent races and/or deadlocks, but they either require special language support or strict discipline on the part of programmers. Here I present a solution based on a well-known deadlock-avoidance protocol and show how it can be enforced by the compiler. It can be applied to programs in which the number of locks is fixed and known up front."
HT: Ted Roth