Strategic Reactor Allocation for Deadlock-Free Execution

As it becomes harder to increase the computation power of a single machine, we are turning towards parallel and distributed systems to extract additional performance by breaking down the problem into pieces and solving it simultaneously. While this provides a great opportunity for increased performance,e it comes with additional problems not present in the sequential approach. One such problem is deadlock. Deadlock is defined as the state in which program execution stalls because the system has run out of resources to manage and execute the program properly, or there exists some circular dependency in the data between parallel or distributed processes. As distributed and parallel systems become more complex, it becomes harder to detect and account for potential deadlock before the system becomes stuck. A proposed system for deadlock prevention is the Live-P protocol which takes information about all potential program executions apriori and annotates a representative DAG to only dispatch tasks when deadlock is impossible. While Live-P is effective at ensuring a deadlock free system it makes certain assumptions about the allocation of tasks to sites that has the potential to create false negatives in the system where Live-P says deadlock is unavoidable but this is due more to a sub-optimal allocation on the system rather than the system itself. We propose a strategy for allocating tasks to sites in these DAG representations of parallel or distributed execution to maximize feasibility while maintaining the Live-P guarantees on deadlock avoidance and liveness.