Perfect Matching with Few Link Activations

We consider the problem of computing a perfect matching problem in a synchronous distributed network, where the network topology corresponds to a complete bipartite graph. The communication between nodes is restricted to activating communication links, which means that instead of sending messages containing a number of bits, each node can only send a pulse over some of its incident links in each round. In the port numbering model, where nodes are unaware of their neighbor’s IDs, we give a randomized algorithm that terminates in Ologn rounds and has a pulse complexity of Onlogn, which corresponds to the number of pulses sent over all links. We also show that randomness is crucial in the port numbering model, as any deterministic algorithm must send at least Ωn² messages in the standard LOCAL model, where the messages can be of unbounded size. Then, we turn our attention to the KT₁ assumption, where each node starts out knowing its neighbors’ IDs. We show that this additional knowledge enables significantly improved bounds even for deterministic algorithms. First, we give an Ologn time deterministic algorithm that sends only On pulses. Finally, we apply this algorithm recursively to obtain an exponential reduction in the time complexity to Olog^∗nloglogn, while slightly increasing the pulse complexity to Onlog^∗n. All our bounds also hold in the standard CONGEST model with single-bit messages.