A tree generating algorithm for designing optimal hierarchical distributed systems
Dorota M. Huizinga, Ewa Kubicko · 1997
Distributed hierarchicalarchitectures have been investigated with regard to specific computational models such as optimization of end-to-end delays in multimedia conferencing or minimization of message overhead in homogenous and heterogenous node clusters.Due to its complexity, the design and analysis of optimal hierarchical distributed systems is usually limited to very specific computational models and optimization criteria.In this paper an alternative approach is taken; a universal technique for finding optimal hierarchical communication systems, applicable to different computational models is proposed.The method is based on an efficient analysis of all rooted trees of a given order, and its computational complexity outperforms all previously existing algorithms.The paper describes the technique and its applications.The successful implementation of the method allowed for experimentation with several case studies.The results of some experiments led to several observations and generalizations, and ultimately allowed ermission to make digital or hard copies of part or all of this work for :sonal or chLssroom use is granted without lee provided that copies are not lde or distribt, ted Ibr profit or commercial advantage and that copies bear s notice and the full citation on the first page.Copyrights for components this work owned by others than ACM must be honored.Abstracting with .'dit is permitted.I'o copy' otherwise, to republish, to post on servers or to listribute to lists, requires prior specific permission and/or a lee.'" 19{)7