search

dtqec / anatevka

A distributed blossom algorithm for minimum-weight perfect matching
MIT License
7 stars 1 forks source link

Rename forward/finish to broadcast/convergecast #16

Open karalekas opened 4 years ago

karalekas commented 4 years ago

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.

ecpeterson commented 4 years ago

See also https://github.com/eigenwareqc/anatevka/pull/204#discussion_r448505858 .

ecpeterson commented 3 years ago

Is this a good idea without doing all of dtqec/anatevka#5 ? Would we want to use the broadcast language without actually using aether's broadcast framework?