2-graph-algs_zy 消息传递系统与洪泛算法.pptVIP

Basic Algs in Message-passing Systems Broadcast and Convergecast on a Spanning Tree Flooding and Building a Spanning Tree Constructing a DFS Spanning Tree for a Specified Root Constructing a DFS Spanning Tree without a Specified Root Broadcast Over a Rooted Spanning Tree Suppose processors already have information about a rooted spanning tree of the communication topology tree: connected graph with no cycles spanning tree: contains all processors rooted: there is a unique root node Implemented via parent and children local variables at each processor indicate which incident channels lead to parent and children in the rooted spanning tree Broadcast Over a Rooted S.T. root initially sends M to its children when a processor receives M from its parent sends M to its children terminates (sets a local boolean variable to be true) Complexity Analysis Synchronous model: time is depth of the spanning tree, which is at most n - 1 number of messages is n - 1, since one message is sent over each spanning tree edge Asynchronous model: same time and messages Convergecast Again, suppose a rooted spanning tree has already been computed by the processors parent and children variables at each processor Do the opposite of broadcast: leaves send messages to their parents non-leaves wait to get message from each child, then send combined info to parent Convergecast Finding a Spanning Tree Given a Root Having a spanning tree is very convenient. How do you get one? Suppose a distinguished processor is known, to serve as the root. Modify the flooding algorithm… Finding a Spanning Tree Given a Root root sends M to all its neighbors when non-root first gets M set the sender as its parent send parent msg to sender send M to all other neighbors (if no other neighbors, then terminate) when get M otherwise send reject msg to sender use parent and reject msgs to set children variables and know when to terminate (after hearing from all neighbors) Execution of Spanning Tree Alg. Execution