1,029
views
0
recommends
+1 Recommend
1 collections
    0
    shares

      Studying business & IT? Drive your professional career forwards with BCS books - for a 20% discount click here: shop.bcs.org

      scite_
       
      • Record: found
      • Abstract: found
      • Conference Proceedings: found
      Is Open Access

      A Simple Distributed Algorithm for the Maintenance of a Spanning Tree

      Published
      proceedings-article
      , ,
      First International Workshop on Verification and Evaluation of Computer and Communication Systems (VECoS 2007) (VECOS)
      Verification and Evaluation of Computer and Communication Systems
      5-6 May 2007
      Distributed computing, failure detectors, fault-tolerance, local knowledge, maintenance, networks, spanning tree, vertex connectivity
      Bookmark

            Abstract

            This work is devoted to the problem of spanning tree maintenance in the presence of crash failures in a distributed environment using only local knowledge. Using a pre-constructed spanning tree of a k -connected graph, we present a protocol to maintain a spanning tree in the presence of k –1 consecutive failures. The contribution of this paper is twofold. First, the problem is formalized as an occurrence of the Menger’s theorem in distributed setting. The second result shows an implementation of the protocol which is composed of a set of modules encoded in the asynchronous message passing model. After each failure occurrence, our algorithm maintains a spanning tree in O(N) time using O(M+N) messages and O(Δ) bits per node. Here Δ is the degree, M the number of edges and N the number of nodes of the graph to be maintained. Furthermore, the studied network is semi-anonymous : Only the root needs to be identified.

            Content

            Author and article information

            Contributors
            Conference
            May 2007
            May 2007
            : 1-14
            Affiliations
            [0001]LaBRI-University of Bordeaux-1

            351, cours de la libération

            Talence, 33405, France
            Article
            10.14236/ewic/VECOS2007.5
            b7b4d677-1087-4a40-baa7-6ab2306565d4
            © Brahim Hamid et al. Published by BCS Learning and Development Ltd. First International Workshop on Verification and Evaluation of Computer and Communication Systems (VECoS 2007), Algiers, Algeria

            This work is licensed under a Creative Commons Attribution 4.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

            First International Workshop on Verification and Evaluation of Computer and Communication Systems (VECoS 2007)
            VECOS
            1
            Algiers, Algeria
            5-6 May 2007
            Electronic Workshops in Computing (eWiC)
            Verification and Evaluation of Computer and Communication Systems
            History
            Product

            1477-9358 BCS Learning & Development

            Self URI (article page): https://www.scienceopen.com/hosted-document?doi=10.14236/ewic/VECOS2007.5
            Self URI (journal page): https://ewic.bcs.org/
            Categories
            Electronic Workshops in Computing

            Applied computer science,Computer science,Security & Cryptology,Graphics & Multimedia design,General computer science,Human-computer-interaction
            failure detectors,fault-tolerance,Distributed computing,local knowledge,maintenance,networks,spanning tree,vertex connectivity

            Comments

            Comment on this article