Mutual exclusion is an algorithmic requirement that no two concurrent processes access a particular resource at the same time. In their paper “Tight Time-Space Tradeoff for Mutual Exclusion,” Prasad Jayanti, Nikhil Bansal, Vibhor Bhatt, and Ranganath Kondapally derive bounds on the tradeoff between remote memory references (RMR) and space for mutual exclusion.
Mutual exclusion algorithms are often complicated by system details like the asynchrony of the processes or inconsistencies that may arise from having shared resource data stored locally in the caches of the processes.
Consider the situation in which n ≥ 2 processes running in parallel share a resource that can only be accessed by one process at a time. The challenge of mutual exclusion is to design an algorithm that upholds two properties: (i) at most one process is accessing the resource at any time, and (ii) every process trying to access the resource is eventually able to do so.
Mutual exclusion algorithms are often complicated by system details like the asynchrony of the processes or inconsistencies that may arise from having shared resource data stored locally in the caches of the processes.
When evaluating the time complexity of such an algorithm, one typically counts the number of “remote memory references,” which occur when a process accesses a shared variable that lies in remote memory. The RMR complexity of a mutual exclusion algorithm is the worst-case number of RMRs that a process must make either in trying to access the resource or in giving up its access to the resource.
Big-O notation describes how fast a function grows or declines with respect to a particular variable. One of the goals of the study was to determine whether there existed a mutual exclusion algorithm that could achieve O(1) space and O(1) RMR complexity while satisfying mutual exclusion criteria. Using a simple game with the complex problem of mutual exclusion, the authors attempted to determine whether the bounds for the simple game could yield bounds for mutual exclusion.
The game, called the “bin-pebble game,” is a single player game in which there are m bins numbered 1,2,…,m. There are initially n pebbles in the first bin. In each step of the game, the player first picks a non-empty bin and shakes it. This causes a pebble to disappear from this bin and allows the player to redistribute the remaining pebbles among the bins in any way. One pebble disappears during each turn, so there will be no pebbles after n turns have elapsed and the game will be over. Finally, in shaking a bin with i pebbles inside it, the player must pay a cost of i. The player wishes to play the game at minimal cost.
Ultimately, the authors derived lower and upper bounds on the cost of the bin pebble game. They then proved that an n pebble, m bin game of total cost t is possible if and only if there is a mutual exclusion algorithm with n processes and m shared variables with t RMR complexity. This reduction of the mutual exclusion problem to the bin pebble game allowed them to derive the following bounds for the RMR complexity of mutual exclusion algorithms:
Lower bound:
Ω(max(n1/m,log(n)/log(m)))
Upper bound:
O(mn1/(m-2)) when m=O(log n)
O(log(n)/log(m)) when m=Ω(log(1+α)n) for any real constant α > 0.
Significantly, the authors imply with these bounds that a mutual exclusion algorithm with O(1) space and O(1) RMR complexity is impossible.
Sources:
1. Bansal N, Bhatt V, Jayanti P, Kondapally R (May 2012). Tight Time-Space Tradeoff for Mutual Exclusion. STOC 2012. Retrieved from http://dl.acm.org/citation.cfm?id=2214065.