You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
From my readings on distributed algorithms (e.g. these Yale course notes) there is a common pattern wrt gathering information about a distributed network, which looks a lot like our FORWARD-SCAN/SCAN/PING/FINISH-SCAN paradigm, called broadcast and convergecast. In these algorithms, the root of a distributed tree tells all of its leaves to gather some information (broadcast) and then the leaves relay that information back up the tree, with some protocol for merging the information as it is aggregated up the tree (convergecast). This is essentially what we're doing to come up with a supervisor recommendation, but the root and internal (non-leaf) nodes also participate in the information-gathering, and our protocol (unify-pongs) is homogeneously applied to both the gathering (PING) and aggregating (pong throw) stages.
One thing: It's important to note that FINISH-SCAN actually serves two functions: (1) if we were told to scan (i.e. if we're not the root), it just sends our pong up the tree (and then it's merged as part of a sync receive in FORWARD-SCAN) and (2) if we initiated the scan (i.e. we are the root), it uses the merged info to spawn a supervisor. We might be able to break these up into two commands.
Random note: the root necessarily has to gather (PING) after all of its children in order for its information to be merged into the final recommendation.
The text was updated successfully, but these errors were encountered:
From my readings on distributed algorithms (e.g. these Yale course notes) there is a common pattern wrt gathering information about a distributed network, which looks a lot like our
FORWARD-SCAN
/SCAN
/PING
/FINISH-SCAN
paradigm, called broadcast and convergecast. In these algorithms, the root of a distributed tree tells all of its leaves to gather some information (broadcast) and then the leaves relay that information back up the tree, with some protocol for merging the information as it is aggregated up the tree (convergecast). This is essentially what we're doing to come up with a supervisor recommendation, but the root and internal (non-leaf) nodes also participate in the information-gathering, and our protocol (unify-pongs
) is homogeneously applied to both the gathering (PING
) and aggregating (pong throw) stages.One thing: It's important to note that
FINISH-SCAN
actually serves two functions: (1) if we were told to scan (i.e. if we're not the root), it just sends our pong up the tree (and then it's merged as part of a sync receive inFORWARD-SCAN
) and (2) if we initiated the scan (i.e. we are the root), it uses the merged info to spawn a supervisor. We might be able to break these up into two commands.Random note: the root necessarily has to gather (
PING
) after all of its children in order for its information to be merged into the final recommendation.The text was updated successfully, but these errors were encountered: