Orderlock: A New Type of Deadlock and its Implications on High Performance Network Protocol Design

In the pursuit of designing high-performance network (HPN) protocols, three critical features for effective transmission have been extensively studied: In-order Delivery, Lossless Transmission, and Out-of-order Capability. However, no practical implementation has successfully achieved all three simultaneously. We identify and prove that the simultaneous realization of these features constitutes a necessary and sufficient condition for a new type of deadlock, which we term Orderlock. We demonstrate that operating in an Orderlock-risky network is impractical and conduct a comprehensive exploration and comparison of Orderlock-free protocols, through a case study tuning AI workload performance. From an Orderlock-prevention perspective, our findings provide insights into the requirements for future HPN protocol and hardware designs.