Peinado, Marcus; Lengauer, Thomas Parallel ‘go with the winners’ algorithms in distributed memory models. (English) Zbl 1053.68124 J. Parallel Distrib. Comput. 63, No. 9, 801-814 (2003). Summary: We parallelize the ‘go with the winners’ algorithm of D. Aldous and U. Vazirani [in: Proceedings of the 35th IEEE Symposium on the Foundations of Computer Science, IEEE Computer Society Press, Silver Spring., MD, 492–501 (1994)] and analyze the resulting parallel algorithm in the LogP-model. The main issues in the analysis are load imbalances and communication delays. The result of the analysis is a practical algorithm which, under reasonable assumptions, achieves linear speedup. Finally, we analyze our algorithm for a concrete application: generating models of amorphous chemical structures. MSC: 68W10 Parallel algorithms in computer science 68M20 Performance evaluation, queueing, and scheduling in the context of computer systems Keywords:Parallel algorithms; Go with the winners; LogP model; Second moment method; Load balancing; Amorphous solids; Self-avoiding walks PDFBibTeX XMLCite \textit{M. Peinado} and \textit{T. Lengauer}, J. Parallel Distrib. Comput. 63, No. 9, 801--814 (2003; Zbl 1053.68124) Full Text: DOI