Interconnection Networks: Graph- and Group Theoretic Modelling

31 pages.International audienceThe present paper surveys recent and promising results about graph--theoretic and group--theoretic modelling in distributed computing. The specific behaviour of various classes of networks (Cayley and Borel Cayley networks, de Bruijn and Kautz networks, etc.) is studied in terms of usual efficiency requirements, such as computability, symmetry, uniformity and algebraic structure, ease of routing, fault-robustness, flexibility, etc. We also address various problems arising from the application of the notion of sense of direction on several significant network topologies. A rough approximation of a ''measure of density'' of networks is proposed. It leads to a conjecture about the real impact of sense of direction with respect to Leader Election. The notion of the dynamic and static symmetry of networks is also considered from the viewpoint of checking and measuring the effects of orientation on the communication complexity of ''consensus protocols''. On the whole, this paper attempt to survey the state of the art in the domain and offer some fruitful directions of research