Applying Static Network Protocols to Dynamic Networks

This paper addresses the problem of how to adapt an algorithm designed for fixed topology networks to produce the intended results, when run in a network whose topology changes dynamically, in spite of encountering topological changes during its execution. We present a simple and unified procedure, called a reset procedure, which, when combined with the static algorithm, achieves this adaptation. The communication and time complexities of the reset procedure, per topological change, are independent of the number of topological changes and are linearly bounded by the size of the subset of the network which participates in the algorithm.

Authors

• Yehuda Afek
• Baruch Awerbuch
• Eli Gafni

Keywords

• Protocols
• Network topology
• Change detection algorithms
• Distributed algorithms
• Contracts
• Algorithm design and analysis
• Data communication
• Termination of employment
• ARPANET
• Delay
• Dynamic Network
• Communication Protocol
• Static Network
• Time Complexity
• Topological Changes
• Static Algorithm
• Communication Network
• Distribution System
• Global Status
• Sequence Changes
• Management Process
• Network Size
• Tree Branches
• Complex Procedures
• Time Stamp
• Communication Patterns
• Distributed Algorithm
• Input-output Relationship
• Algorithm Execution
• Change In The Total Number
• Response Message
• Final Input
• Infinite Interval
• Spanning Tree
• Message Transmission
• Partial Order
• Part Of Network
• Local Procedures