Deadlock

Deadlock and livelock are two of the most frightening terms when discussed with anyone knowledgeable about the field of computing. As a quick refresher, deadlock is defined as when two separate tasks (threads) on a machine are waiting for the other to finish before progress is made (and thus neither ever finishes). (“Deadlock”) Similarly, livelock is defined as the situation where processes (or threads) change states, but only with respect to each other with no actual progress on the task at hand made. (“Deadlock) When either one of these situations (or under even more extreme circumstances both of these situations) occur, the effects can be devastating (both to the performance of the machine itself and the programmer’s sanity). The effects are even more devastating when these situations occur on distributed systems as many of the problems of single machine systems are amplified on them. The computing community, under ideal circumstances, could rest easy as Gill, et al. present their proposed solution to these problems when they occur on distributed systems in their work Efficient Distributed Deadlock Avoidance with Liveness Guarantees. This is good, right? These problems have been solved so the programming community can move on to other problems. Not necessarily so, for the solution proposed by Gill, et al. is based on some questionable assumptions. It is of utter importance that Gill and his colleagues make it quite clear their algorithm is effective if and only if the scheduler is fair. In this essay, the proposed solution by Gill, et al. will be examined under an ethical lens to determine if the way it is presented is in line with major ethical theories.

Other solutions to deadlock and livelock have been proposed before the solution designed by Gill, et al. All of these previously proposed solutions had one common problem- the overhead (specifically the overhead relating to inter-process communication) made each individual solution so impractical that...