We consider the problem of waking up n processors of a completely broadcast system. We analyze this problem in both globally and locally synchronous models, with or without n being known to processors and with or without labeling of processors. The main question we answer is: how fast we can wake all the processors up with probability 1 - ε in each of these eight models. In [10] a logarithmic waking algorithm for the strongest set of assumptions is described, while for weaker models only linear and quadratic algorithms were obtained. We prove that in the weakest model (local synchronization, no knowledge of n or labeling) the best waking time is O(n/log n). We also show logarithmic or polylogarithmic waking algorithms for all stronger models, which in some cases gives an exponential improvement over previous results.
展开▼
机译：我们考虑唤醒完全广播系统的N处理器的问题。我们在全球和局部同步模型中分析此问题，或者没有N是由处理器和或没有处理器的标签而已知的n。我们回答的主要问题是：在这八种型号中的每一个中，我们如何快速将所有处理器唤醒所有处理器。在[10]中，描述了用于最强的假设集的对数唤醒算法，而对于较弱的模型，仅获得线性和二次算法。我们证明，在最薄弱的模型中（局部同步，NO NOR NURTS的知识）最好的醒来时间是O（n / log n）。我们还显示所有更强大的模型的对数或电动机扫描算法，在某些情况下，在某些情况下给出了对先前结果的指数改进。
展开▼
