Distributed Computation in Node-Capacitated Networks

Exploration of communication primitives and algorithms in node-capacitated networks, including Node-Capacitated Clique Model, communication on butterfly networks, orientation using Boruvka's algorithm, computing O(a)-orientation, and solving graph problems like BFS trees, maximal independent set, maximal matching, and O(a)-coloring through multicast trees.

• Distributed Computation
• Node-Capacitated Networks
• Communication Primitives
• Algorithms
• Multicast Trees

zsazsa Follow

Uploaded on Aug 03, 2024 | 0 Views

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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Distributed Computation in Node-Capacitated Networks John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, Fabian Kuhn, and Jason Li Presentation by Joseph Oglio

2. Node-Capacitated Clique Model Congested Clique Model Each node can send O(logn) bits Each node can send and receive up to O(logn) messages in each round (additional received are dropped) Nodes are interconnected by a complete graph (n) bits may be sent in a single round Synchronous Each node can send O(logn) bits Each node may communicate to (n) other nodes in each round Nodes are interconnected by a complete graph (n^2) bits may be sent in a single round Synchronous

3. Communication Primitive - Aggregate and Broadcast Communication is done on a butterfly network Aggregate and Broadcast is achieved by flooding messages down the butterfly, once hitting the bottom level they are combined and sent up to the node

4. a ) - O R I E N T A T I O N MST They utilize Boruvka s algorithm with Heads Tails clustering in which every separate cluster finds its minimum edge to the other clusters and flips a coin If the coin flip of this cluster is different from the other cluster, they join to the heads flip With high probability this takes O(logn) iterations

5. Computing an O(a)-orientation The algorithm repeatedly identifies low-degree nodes which are removed from the graph until the graph is empty. When a node leaves, all its incident edges are directed away from it This is done using a 3 stage algorithm: In Stage 1, every node determines whether it is active which determines if the node is of low-degree In Stage 2, every active node learns which of its neighbors are inactive In Stage 3, every active node learns which of its remaining neighbors are active or waiting.

6. Remaining Graph Problems Breadth-First Search Trees, Maximal Independent Set, Maximal Matching, and O(a)-Coloring all rely on precomputed multicast trees to route messages in the network These multicast trees are formed using the O(a)-orientation algorithm by having nodes join their outneighbors tree, this takes O(a + logn) time Then using all the previously defined communication primitive and the multicast tree the remaining graph problems are solved with conventional solutions

7. Algorithmic Results