@inproceedings{sitchinava-soda21,
  author = "Michael T. Goodrich and Riko Jacob and Nodari Sitchinava",
  title  = "Atomic power in forks: a super-logarithmic lower bound for implementing butterfly networks in the Nonatomic Binary Fork-Join model",
  booktitle = "Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms",
  series = "SODA '21",
  month = "1",
  year = "2021",
  pages = "2141-2153",
  doi = "10.1137/1.9781611976465.128",
  abstract = "We prove an $\Omega(\log n \log \log n)$ lower bound for the span of implementing the $n$ input, $\log n$-depth FFT circuit (also known as butterfly network) in the nonatomic binary fork-join model.  In this model, memory-access synchronizations occur only through fork operations, which spawn two child threads, and join operations, which resume a parent thread when its child threads terminate.  Our bound is asymptotically tight for the nonatomic binary fork-join model, which has been of interest of late, due to its conceptual elegance and ability to capture asynchrony.  Our bound implies super-logarithmic lower bound in the nonatomic binary fork-join model for implementing the butterfly merging networks used, e.g., in Batcher's bitonic and odd-even mergesort networks.  This lower bound also implies an asymptotic separation result for the atomic and nonatomic versions of the fork-join model, since, as we point out, FFT circuits can be implemented in the atomic binary fork-join model with span equal to their circuit depth."
}