Abstract
Many fundamental problems in shared-memory distributed computing, including mutual exclusion [8], consensus [18], and implementations of many sequential objects [14], are known to require linear space in the worst case. However, these lower bounds all work by constructing particular executions for any given algorithm that may be both very long and very improbable. The significance of these bounds is justified by an assumption that any space that is used in some execution must be allocated for all executions. This assumption is not consistent with the storage allocation mechanisms of actual practical systems.
Type
Publication
In International Symposium on Distributed Computing
Alex Tong
Postdoctoral Fellow
My research interests include flow models and optimal transport applied to cells and proteins.