Interview question

Design an all-gather communication schedule for n GPUs ranked 0 through n - 1. Initially GPU i owns exactly one data block, identified by i. After communication, every GPU must possess all blocks 0 through n - 1. Communication occurs in synchronous rounds. In each round, a GPU may send one block to at most one other GPU and receive one block from at most one other GPU, simultaneously if needed. A GPU cannot send to itself. All sends occur simultaneously, and a GPU may send only a block it possessed before the round began; newly received blocks become available in the next round. Each message contains exactly one block, and any GPU may communicate directly with any other GPU. Provide a predefined formula specifying, for each round t and GPU i, which block it sends and to which GPU, without keeping state.