Broadcast Algorithms for HARTS: Reliable Solutions with Virtual Cut-Through Switching
Delve into the world of broadcast algorithms developed for multicomputer systems with hexagonal mesh topology, ensuring reliable message delivery through disjoint paths and addressing byzantine nodes. Ideal for applications in clock synchronization and distributed agreement during faults.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Reliable Broadcast Algorithms for HARTS AUTHORS: DILIP D. KANDLUR AND KANG G. SHIN
Goal Create a set of broadcast algorithms developed for a multicomputer system with hexagonal mesh topology, using virtual cut-through switching. The algorithms deliver multiple copies of a message from a source node to every other node through disjoint paths. Can be used for broadcasting in presence of byzantine nodes whose identities are not known. Motivation: Applications in clock synchronization and distributed agreement in presence of faults
Hexagonal Mesh Topology
Operation takes place at the link level Designed to reduce store-and-forward communication Packet header contains info for handling broadcasts messages, (e.g. type, distance, step, and tag) Broadcast Primitive Routing controller examines tags of the packet for nonzero values, and whether the corresponding link is available. Routing tags are updated to reflect the new distance to its destination.
Broadcast Primitive Deliver refers to the delivery of the packet by the link controller to the processor. Send_on_link relays the packet to the next node in the same direction in which it arrived.
BCAST_INIT Executed by the source node Common to all broadcasting algorithms Sends packet in each available direction, for the entire diameter of the hexagonal mesh.
SBCAST_RELAY As a result of the RELAY primitive, the packet is sent along two axes: the opposite of the direction the packet was received on, and the axis next to it.
Multiple Copy Broadcast Algorithms that deliver k copies of a message to each node using disjoint paths. Used in place of acknowledgment-retry.
2-BCAST Similar to SBCAST_RELAY, but the message is forwarded in two directions After packet reaches edge, sent forward n-1 steps
3-BCAST Nodes on the principal axes transmit the message left for n-1 steps. Extreme nodes on the axes transmit the packet n-1 steps left.
6-BCAST 4-BCAST and 5-BCAST are restricted forms of 6-BCAST Uses a tag field to ensure only relevant nodes execute an additional forwarding step. Nodes on the extremities of the principal axes use tags A and B . The immediate neighbors of the broadcast source node with packet.distance of n-2, use tags C and D
(4-)6-BCAST Algorithm
Algorithm Analysis Latency is dependent on system load and number of cut-through routes. Time required to transmit a packet of length M: S + rM S is packet set-up time and r is transmission rate of the link When a packet cutes through a node, delay experienced is the time taken to receive and examine the header, a small constant, d. S + rM + id Where i is the number of cut through nodes Best case for SBCAST is: 2S + 2rM + (n-3)d If the network is otherwise idle
Algorithm Analysis Average-case broadcast latency for Algo. A is (l + 1)(S + rM) + (3n^2 3n 1 l)d Where l = (3n(n -1) -1)p Algorithm A is the RELAY primitive, using send_packet with a distance of 3n(n-1) p = utilization of each link
Simulation Results Compared to SBCAST 1 clock cycle = 1.5 s
Thoughts Useful due to the algorithms simplicity and efficient use of virtual cut-through. Relevant to real-time systems where the time overhead of identifying all faulty processors cannot be tolerated. Can be applied to wrapped rectangular meshes.
