Distribute a Large Matrix Transpose

# Distribute a Large Matrix Transpose A square matrix is too large for one machine. Design how independent workers on multiple machines can compute its transpose, including data partitioning, task assignment, output placement, retries, and validation. ### Constraints & Assumptions - Workers are separate machines, not threads sharing one address space. - The matrix representation and storage layout must be stated. - A failed or duplicated task must not corrupt the final transpose. ### Clarifying Questions to Ask - Is the matrix dense or sparse, and how is it stored? - Can workers write directly to the destination store? - What memory, network, and skew constraints dominate? ```hint Transpose tiles Reason about rectangular blocks whose source and destination coordinates can be named independently. ``` ### What a Strong Answer Covers - A partition scheme with bounded worker memory. - Task metadata mapping each source block to its transposed destination. - Idempotent writes, retry behavior, progress tracking, and straggler handling. - Network cost, validation, and treatment of diagonal and edge blocks. ### Follow-up Questions 1. How would the design change for a sparse matrix? 2. Can the input and output be streamed without materializing both matrices?