A network model of Barrier synchronization algorithms (Q1186097)

We consider two algorithms for the barrier synchronization of \(N\) processes: the dissemination algorithm and Brooks algorithm in \textit{E. D. Brooks} [Int. J. Parallel Program. 15, 295-307 (1986; Zbl 0641.68010)] and \textit{D. Heusgen}, \textit{R. Finkel} and \textit{U. Mauber} [Int.J. Parallel Program. 17(1), 1-17 (1988; Zbl 0662.68008)]. Both algorithms comprise a number of binary communications amongst the processes, organized into a sequence of stages. It is shown that Brooks' algorithm requires between \(\hbox{Log} N(\lceil\log_ 2 N\rceil)\) and \(2 \hbox{Log} N\) stages, the lower bound being guaranteed only in the case that \(N\) is a power of 2 (cubic) and the upper bound seemingly needed for most other \(N\). On the other hand, it is shown that the dissemination algorithm requires only \(\hbox{Log} N\) stages regardless of \(N\), making it apparently superior to the Brooks algorithm. We introduce a network model of local barrier algorithms. Using it we obtain a rigorous correctness proof for local barrier algorithms, and show that the number of states in the Brooks algorithm is bounded above by \(\hbox{Log} N+1\). The Brooks algorithm is therefore essentially equivalent in time complexity to the dissemination algorithm. We then address the question of which values of \(N\) admit exactly \(\hbox{Log} N\) Brooks stages. We find a sufficient condition, and conjecture that it is also necessary.