2001 · 20 citations · 11 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer ArchitectureTheory Of ComputationCommunication ComplexityDistributed Memory SystemsDistributed Mutual ExclusionRemote Memory AccessSynchronization PrimitivesLower Bound ComputationLower Bound TechniquesMutual ExclusionPolynomial Time Complexity
We establish a lower bound of 23 N= log log N) remote memory references for N-process mutual exclusion algorithms based on reads, writes, or comparison primitives such as test-and-set and compareand -swap. Our bound improves an earlier lower bound of 34 log N= log log log N) established by Cypher. Our lower bound is of importance for two reasons. First, it almost matches the (log N) time complexity of the best known algorithms based on reads, writes, or comparison primitives. Second, our lower bound suggests that it is likely that, from an asymptotic standpoint, comparison primitives are no better than reads and writes when implementing local-spin mutual exclusion algorithms. Thus, comparison primitives may not be the best choice to provide in hardware if one is interested in scalable synchronization.
11
On an extremal problem in graph theory
Péter L. Erdős · Colloquium Mathematicum · 1964 · 676 citations · Full text