Edges-disjoint spanning trees on the binary wrapped butterfly network with applications to fault tolerance

Abderezak Touzene*

*المؤلف المقابل لهذا العمل

نتاج البحث: المساهمة في مجلةArticleمراجعة النظراء

4 اقتباسات (Scopus)


In many parallel applications, the need for broadcasting, scattering, gathering or gossiping is crucial. Many collective communication algorithms have been studied for different topologies of interconnection networks such as hypercubes, meshes, De Bruijn and star graphs. In this paper we study some communication procedures on the binary wrapped butterfly BWB(n) of dimension n interconnection networks. We consider the BWB(n) as a point-to-point interconnection network. Communication is assumed to be full duplex, all-ports with a linear communication model and is based on store-and-forward techniques. The BWB(n) is a constant degree 4 Cayley graph. Vadapalli and Srimani gave a new representation of the BWB(n) that bring some convenience in studying the topological properties and fault tolerance. Using this new representation, we propose an improved one-to-all broadcast algorithm, based on a spanning tree of optimal height. We present a technique based on rotative trees for constructing multiple spanning trees that would be used to derive: a fault tolerant one-to-all broadcast, a scattering, a gathering algorithms and theirs fault tolerant version.

اللغة الأصليةEnglish
الصفحات (من إلى)649-666
عدد الصفحات18
دوريةParallel Computing
مستوى الصوت28
رقم الإصدار4
المعرِّفات الرقمية للأشياء
حالة النشرPublished - أبريل 2002

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???
  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1708???
  • ???subjectarea.asjc.1700.1705???
  • ???subjectarea.asjc.1700.1704???
  • ???subjectarea.asjc.1700.1702???


أدرس بدقة موضوعات البحث “Edges-disjoint spanning trees on the binary wrapped butterfly network with applications to fault tolerance'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا