Radia Perlman’s poem “Algorhyme” describes how a protocol she designed maintains one of these structures by having network switches exchange BPDU messages. For 10 points each:
[10m] Name these structures that can be found in a graph by considering each node as a connected component, and then iteratively identifying the smallest edge weight between components.
ANSWER: spanning trees [accept minimum spanning trees or MSTs; accept Spanning Tree Protocol; prompt on trees] (BPDU is Bridge Protocol Data Unit. The process described is Borůvka’s algorithm.)
[10e] Perlman’s Spanning Tree Protocol prevents loops in these networks. In these networks, devices within a small geographic region are connected over Ethernet or Wi-Fi.
ANSWER: LANs (“lanz”) [or local area networks]
[10h] Older Ethernet LANs (“lanz”) had a bus topology that required this medium access control method to be used with collision detection. This method allows a machine to transmit only if no transmissions are detected on the bus.
ANSWER: CSMA [or carrier sense multiple access; accept CSMA/CD or carrier sense multiple access with collision detection; accept CSMA/CA or carrier sense multiple access with collision avoidance]
<Other Science>