NDLI: The distributed spanning tree: a scalable interconnection topology for efficient and equitable traversal

Content Provider	IEEE Xplore Digital Library
Author	Dahan, S. Nicod, J.-M. Philippe, L.
Copyright Year	2005
Description	Author affiliation: Lab. d'Informatique, Univ. de Franche-Comte, Besangon, France (Dahan, S.; Nicod, J.-M.; Philippe, L.)
Abstract	Peer-to-peer and grid applications currently have few structures that allow efficient discovery mechanisms in large scale system. The trees can be an appropriate structure for this task. However, the tree's bottlenecks are a significant drawback in large scale architectures and connected graphs are used most of the time. In this paper, we propose an appropriate architecture named distributed spanning tree (DST) to allow discovery in large scale environment. This structure is organized into a hierarchy of groups. The nodes are put together in groups and groups are gathered in groups of higher level, recursively. This organization, built on top of routing tables allows the instantaneous creation of spanning trees rooted by any nodes and keeps the load balanced between the nodes. The first studies about the distributed spanning tree suggest that it has all the advantages of a tree without its drawbacks. This can be explained by the following complexity order: each node stores only O(log(n)) information; a parallel traversal needs n - 1 messages and takes O(log(n)) units of time; adding or removing a node needs O(n) messages in the worst case but only needs in average O(log(n)) messages. Load balancing and fault tolerance are ensured by the architecture of the distributed spanning tree itself.
Starting Page	243
Ending Page	250
File Size	2935172
Page Count	8
File Format	PDF
ISBN	0780390741
DOI	10.1109/CCGRID.2005.1558561
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-05-09
Publisher Place	United Kingdom
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Topology Peer to peer computing Tree graphs Scalability Large-scale systems Routing Load management Fault tolerance Message passing Multicast algorithms
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in