The 28th ACM Symposium on Operating Systems Principles
October 25-28, 2021

Accepted Papers

The following papers have been accepted to appear at the 28th ACM SIGOPS Symposium on Operating Systems Principles (SOSP), conditional on the approval of each paper's shepherd:

Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3 by James Bornholt (Amazon Web Services & The University of Texas at Austin), Rajeev Joshi (Amazon Web Services), Vytautas Astrauskas (ETH Zurich), Brendan Cully (Amazon Web Services), Bernhard Kragl (Amazon Web Services), Seth Markle (Amazon Web Services), Kyle Sauri (Amazon Web Services), Drew Schleit (Amazon Web Services), Grant Slatton (Amazon Web Services), Serdar Tasiran (Amazon Web Services), Jacob Van Geffen (University of Washington), and Andrew Warfield (Amazon Web Services)

Boki: Stateful Serverless Computing with Shared Logs by Zhipeng Jia (The University of Texas at Austin) and Emmett Witchel (The University of Texas at Austin)

ghOSt: Fast & Flexible User-Space Delegation of Linux Scheduling by Jack Tigar Humphries (Google), Neel Natu (Google), Ashwin Chaugule (Google), Ofir Weisse (Google), Barret Rhoden (Google), Josh Don (Google), Luigi Rizzo (Google), Oleg Rombakh (Google), Paul Turner (Google), and Christos Kozyrakis (Stanford University and Google)

Exploiting Nil-Externality for Fast Replicated Storage by Aishwarya Ganesan (VMware Research), Ramnatthan Alagappan (VMware Research), Andrea Arpaci-Dusseau (University of Wisconsin–Madison), and Remzi Arpaci-Dusseau (University of Wisconsin–Madison)

Log-structured Protocols in Delos by Mahesh Balakrishnan (Facebook), Chen Shen (Facebook), Ahmed Jafri (Facebook), Suyog Mapara (Facebook), David Geraghty (Facebook), Jason Flinn (Facebook), Vidhya Venkat (Facebook), Ivailo Nedelchev (Facebook), Santosh Ghosh (Facebook), Mihir Dharamshi (Facebook), Jingming Liu (Facebook), Filip Gruszczynski (Facebook), Jun Li (Facebook), Rounak Tibrewal (Facebook), Ali Zaveri (Facebook), Rajeev Nagar (Facebook), Ahmed Yossef (Facebook), Francois Richard (Facebook), and Yee Jiun Song (Facebook)

iGUARD: In-GPU Advanced Race Detection by Aditya K Kamath (Indian Institute of Science) and Arkaprava Basu (Indian Institute of Science)

Shard Manager: A Generic Shard Management Framework for Geo-distributed Applications by Sangmin Lee (Facebook), Zhenhua Guo (Facebook), Omer Sunercan (Facebook), Jun Ying (Facebook), Thawan Kooburat (Facebook), Suryadeep Biswal (Facebook), Jun Chen (Facebook), Kun Huang (Facebook), Yatpang Cheung (Facebook), Yiding Zhou (Facebook), Kaushik Veeraraghavan (Facebook), Biren Damani (Facebook), Pol Mauri Ruiz (Facebook), Vikas Mehta (Facebook), and Chunqiang Tang (Facebook)

HEALER: Relation Learning Guided Kernel Fuzzing by Hao Sun (School of Software, Tsinghua University, KLISS, BNRist, China), Yu Heng Shen (School of Software, Tsinghua University, KLISS, BNRist, China), Cong Wang (School of Software, Tsinghua University, KLISS, BNRist, China), Jianzhong Liu (School of Software, Tsinghua University, KLISS, BNRist, China), Yu Jiang (School of Software, Tsinghua University, KLISS, BNRist, China), Ting Chen (Center for Cybersecurity, University of Electronic Science and Technology of China, China), and Aiguo Cui (Huawei Technologies Co Ltd, China)

Syrup: User-Defined Scheduling across the Stack by Kostis Kaffes (Stanford University), Jack Tigar Humphries (Stanford University), David Mazières (Stanford University), and Christos Kozyrakis (Stanford University)

Snowboard: Finding Kernel Concurrency Bugs through Systematic Inter-thread Communication Analysis by Sishuai Gong (Purdue University), Deniz Altınbüken (Google Research), Pedro Fonseca (Purdue University), and Petros Maniatis (Google Research)

HeMem: Scalable Tiered Memory Management for Big Data Applications and Real NVM by Amanda Raybuck (University of Texas at Austin), Tim Stamler (University of Texas at Austin), Wei Zhang (Microsoft), Mattan Erez (University of Texas at Austin), and Simon Peter (University of Texas at Austin)

Cuckoo Trie: Exploiting Memory-Level Parallelism for Efficient DRAM Indexing by Adar Zeitak (Tel Aviv University) and Adam Morrison (Tel Aviv University)

Basil: Breaking up BFT with ACID (transactions) by Florian Suri-Payer (Cornell University), Matthew Burke (Cornell University), Yunhao Zhang (Cornell University), Zheng Wang (Cornell University), Lorenzo Alvisi (Cornell University), and Natacha Crooks (UC Berkeley)

Gradient Compression Supercharged High-Performance Data Parallel DNN Training by Youhui Bai (University of Science and Technology of China), Cheng Li (University of Science and Technology of China), Quan Zhou (University of Science and Technology of China), Jun Yi (University of Nevada at Reno), Ping Gong (University of Science and Technology of China), Feng Yan (University of Nevada at Reno), Ruichuan Chen (Nokia Bell Labs), and Yinlong Xu (University of Science and Technology of China)

TwinVisor: Hardware-isolated Confidential Virtual Machines for ARM by Dingji Li (Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University; Engineering Research Center for Domain-specific Operating Systems, Ministry of Education, China), Zeyu Mi (Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University; Engineering Research Center for Domain-specific Operating Systems, Ministry of Education, China), Yubin Xia (Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University; Engineering Research Center for Domain-specific Operating Systems, Ministry of Education, China), Binyu Zang (Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University; Engineering Research Center for Domain-specific Operating Systems, Ministry of Education, China), Haibo Chen (Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University; Engineering Research Center for Domain-specific Operating Systems, Ministry of Education, China), and Haibing Guan (Shanghai Key Laboratory of Scalable Computing and Systems, Shanghai Jiao Tong University)

Xenic: SmartNIC-Accelerated Distributed Transactions by Henry N. Schuh (University of Washington), Weihao Liang (University of Washington), Ming Liu (University of Wisconsin at Madison/VMware Research), Jacob Nelson (Microsoft Research), and Arvind Krishnamurthy (University of Washington)

Witcher: Systematic Crash Consistency Testing for Non-Volatile Memory Key-Value Stores by Xinwei Fu (Virginia Tech), Wook-Hee Kim (Virginia Tech), Ajay Paddayuru Shreepathi (Stony Brook University), Mohannad Ismail (Virginia Tech), Sunny Wadkar (Virginia Tech), Dongyoon Lee (Stony Brook University), and Changwoo Min (Virginia Tech)

CLoF: A Compositional Lock Framework for Multi-level NUMA Systems by Rafael Lourenco de Lima Chehab (Huawei Dresden Research Center, Huawei OS Kernel Lab, Technische Universität Dresden), Antonio Paolillo (Huawei Dresden Research Center, Huawei OS Kernel Lab), Diogo Behrens (Huawei Dresden Research Center, Huawei OS Kernel Lab), Ming Fu (Huawei Dresden Research Center, Huawei OS Kernel Lab), Hermann Härtig (Technische Universität Dresden), and Haibo Chen (Huawei OS Kernel Lab, Shanghai Jiao Tong University China)

Geometric Partitioning: Explore the Boundary of Optimal Erasure Code Repair by Yingdi Shan (Tsinghua University), Kang Chen (Tsinghua University), Tuoyu Gong (Tsinghua University), Lidong Zhou (Microsoft Research), Tai Zhou (Alibaba Group), and Yongwei Wu (Tsinghua University)

dSpace: Composable Abstractions for Smart Spaces by Silvery Fu (UC Berkeley) and Sylvia Ratnasamy (UC Berkeley)

Formal Verification of a Multiprocessor Hypervisor on Arm Relaxed Memory Hardware by Runzhou Tao (Columbia University), Jianan Yao (Columbia University), Xupeng Li (Columbia University), Shih-Wei Li (Columbia University), Jason Nieh (Columbia University), and Ronghui Gu (Columbia University)

MIND: In-Network Memory Management for Disaggregated Data Centers by Seung-seob Lee (Yale University), Yanpeng Yu (Yale University), Yupeng Tang (Yale University), Anurag Khandelwal (Yale University), Lin Zhong (Yale University), and Abhishek Bhattacharjee (Yale University)

Snoopy: Surpassing the Scalability Bottleneck of Oblivious Storage by Emma Dauterman (UC Berkeley), Vivian Fang (UC Berkeley), Ioannis Demertzis (UC Berkeley, UC Santa Cruz), Natacha Crooks (UC Berkeley), and Raluca Ada Popa (UC Berkeley)

The Aurora Single Level Store Operating System by Emil Tsalapatis (University of Waterloo), Ryan Hancock (University of Waterloo), Tavian Barnes (University of Waterloo), and Ali José Mashtizadeh (University of Waterloo)

Forerunner: Constraint-based Speculative Transaction Execution for Ethereum by Yang Chen (Microsoft Research), Zhongxin Guo (Microsoft Research), Runhuai Li (Zhejiang University and Microsoft Research), Shuo Chen (Microsoft Research), Lidong Zhou (Microsoft Research), Yajin Zhou (Zhejiang University), and Xian Zhang (Microsoft Research)

LineFS: Efficient SmartNIC Offload of a Distributed File System with Pipeline Parallelism by Jongyul Kim (KAIST), Insu Jang (KAIST), Waleed Reda (Université catholique de Louvain / KTH Royal Institute of Technology), Jaeseong Im (KAIST), Marco Canini (KAUST), Dejan Kostić (KTH Royal Institute of Technology), Youngjin Kwon (KAIST), Simon Peter (University of Texas at Austin), and Emmett Witchel (UT Austin)

Regular Sequential Serializability and Regular Sequential Consistency by Jeffrey Helt (Princeton University), Matthew Burke (Cornell University), Amit Levy (Princeton University), and Wyatt Lloyd (Princeton University)

WineFS: a hugepage-aware file system for persistent memory that ages gracefully by Rohan Kadekodi (University of Texas at Austin), Saurabh Kadekodi (Carnegie Mellon University), Soujanya Ponnapalli (University of Texas at Austin), Harshad Shirwadkar (Google), Greg Ganger (Carnegie Mellon University), Aasheesh Kolli (Penn State University and VMware Research), and Vijay Chidambaram (University of Texas at Austin and VMware Research)

Kangaroo: Caching Billions of Tiny Objects on Flash by Sara McAllister (Carnegie Mellon University), Benjamin Berg (Carnegie Mellon University), Julian Tutuncu-Macias (Carnegie Mellon University), Juncheng Yang (Carnegie Mellon University), Sathya Gunasekar (Facebook), Jimmy Lu (Facebook), Daniel Berger (University of Washington/ Microsoft Research), Nathan Beckmann (Carnegie Mellon University), and Gregory R. Ganger (Carnegie Mellon University)

The Demikernel Library OS Architecture for Microsecond, Kernel-Bypass Datacenter Systems by Irene Zhang (Microsoft Research/University of Washington), Amanda Raybuck (University of Texas at Austin), Pratyush Patel (University of Washington), Kirk Olynyk (Microsoft Research), Jacob Nelson (Microsoft Research), Omar S. Navarro Leija (University of Pennsylvania), Ashlie Martinez (University of Washinton), Jing Liu (University of Wisconsin, Madison), Anna Kornfeld Simpson (University of Washington), Sujay Jayakar (Microsoft Research), Pedro Henrique Penna (Microsoft Research), Max Demoulin (University of Pennsylvania), Piali Choudhury (Microsoft Research), and Anirudh Badam (Microsoft)

Rudra: Finding Memory Safety Bugs in Rust at the Ecosystem Scale by Yechan Bae (Georgia Institute of Technology), Youngsuk Kim (Georgia Institute of Technology), Ammar Askar (Georgia Institute of Technology), Jungwon Lim (Georgia Institute of Technology), and Taesoo Kim (Georgia Institute of Technology)

When Idling is Ideal: Optimizing Tail-Latency for Highly-Dispersed Datacenter Workloads with Perséphone by Max Demoulin (University of Pennsylvania), Josh Fried (MIT CSAIL), Isaac Pedisich (University of Pennsylvania), Marios Kogias (Microsoft Research), Boon Thau Loo (University of Pennsylvania), Linh Thi Xuan Phan (University of Pennsylvania), and Irene Zhang (Microsoft Research/University of Washington)

Bladerunner: Stream Processing at Scale for a Live View of Backend Data Mutations at the Edge by Jeff Barber (Facebook), Ximing Yu (Facebook), Laney Kuenzel Zamore (Facebook), Shie Erlich (Facebook), Jerry Lin (Facebook), Vahid Jazayeri (Facebook), Tony Savor (Google), and Michael Stumm (University of Toronto)

IODA: A Host/Device Co-Design for Strong Predictability Contract on Modern Flash Storage by Huaicheng Li (University of Chicago and Carnegie Mellon University), Martin L. Putra (University of Chicago), Ronald Shi (University of Chicago), Xing Lin (NetApp), Gregory R. Ganger (Carnegie Mellon University), and Haryadi S. Gunawi (University of Chicago)

BIDL: A High-throughput, Low-latency Permissioned Blockchain Framework for Datacenter Networks by Ji Qi (The University of Hong Kong), Xusheng Chen (The University of Hong Kong), Yunpeng Jiang (The University of Hong Kong), Jianyu Jiang (The University of Hong Kong), Tianxiang Shen (The University of Hong Kong), Shixiong Zhao (The University of Hong Kong), Sen Wang (Huawei Technologies Co., Ltd.), Gong Zhang (Huawei Technologies Co., Ltd.), Li Chen (Huawei Technologies Co., Ltd.), Man Ho Au (The University of Hong Kong), and Heming Cui (The University of Hong Kong)

Random Walks on Huge Graphs at Cache Efficiency by Ke Yang (Tsinghua Unversity & Qatar Computing Research Institute, HBKU & Beijing HaiZhi XingTu Technology Co., Ltd.), Xiaosong Ma (Qatar Computing Research Institute, HBKU), Saravanan Thirumuruganathan (Qatar Computing Research Institute, HBKU), Kang Chen (Tsinghua University & Beijing HaiZhi XingTu Technology Co., Ltd.), and Yongwei Wu (Tsinghua University & Beijing HaiZhi XingTu Technology Co., Ltd.)

Birds of a Feather Flock Together : Scaling RDMA RPCs with FLOCK by Sumit Kumar Monga (Virginia Tech), Sanidhya Kashyap (EPFL), and Changwoo Min (Virginia Tech)

Understanding and Detecting Software Upgrade Failures in Distributed Systems by Yongle Zhang (Purdue University), Junwen Yang (University of Chicago), Zhuqi Jin (University of Toronto), Utsav Sethi (University of Chicago), Kirk Rodrigues (University of Toronto), Shan Lu (University of Chicago), and Ding Yuan (University of Toronto)

RAS: Continuously Optimized Region-Wide Datacenter Resource Allocation by Andrew Newell (Facebook), Dimitrios Skarlatos (Facebook/Carnegie Mellon University), Jingyuan Fan (Facebook), Pavan Kumar (Facebook), Maxim Khutornenko (Facebook), Mayank Pundir (Facebook), Yirui Zhang (Facebook), Mingjun Zhang (Facebook), Yuanlai Liu (Facebook), Linh Le (Facebook), Brendon Daugherty (Facebook), Apurva Samudra (Facebook), Prashasti Baid (Facebook), James Kneeland (Facebook), Igor Kabiljo (Facebook), Dmitry Shchukin (Facebook), Andre Rodrigues (Facebook), Scott Michelson (Facebook), Ben Christensen (Facebook), Kaushik Veeraraghavan (Facebook), and Chunqiang Tang (Facebook)

J-NVM: Off-heap Persistent Objects in Java by Anatole Lefort (Télécom SudParis - Institut Polytechnique de Paris), Yohan Pipereau (Télécom SudParis - Institut Polytechnique de Paris), Kwabena Amponsem Boateng (Télécom SudParis - Institut Polytechnique de Paris), Pierre Sutra (Télécom SudParis - Institut Polytechnique de Paris), and Gaël Thomas (Télécom SudParis - Institut Polytechnique de Paris)

Faster and Cheaper Serverless Computing on Harvested Resources by Yanqi Zhang (Cornell University), Inigo Goiri (Microsoft Research), Gohar Irfan Chaudhry (Microsoft Research), Rodrigo Fonseca (Microsoft Research), Sameh Elnikety (Microsoft Research), Christina Delimitrou (Cornell University), and Ricardo Bianchini (Microsoft Research)

Scale and Performance in a Filesystem Semi-Microkernel by Jing Liu (University of Wisconsin–Madison), Anthony Rebello (University of Wisconsin–Madison), Yifan Dai (University of Wisconsin–Madison), Chenhao Ye (University of Wisconsin–Madison), Sudarsun Kannan (Rutgers University), Andrea Arpaci-Dusseau (University of Wisconsin–Madison), and Remzi Arpaci-Dusseau (University of Wisconsin–Madison)

Rabia: Simplifying State-Machine Replication Through Randomization by Haochen Pan (Boston College), Jesse Tuglu (Boston College), Neo Zhou (Boston College), Tianshu Wang (Boston College), Yicheng Shen (Boston College), Xiong Zheng (UT Austin), Joseph Tassarotti (Boston College), Lewis Tseng (Boston College), and Roberto Palmieri (Lehigh University)

Automated SmartNIC Offloading Insights for Network Functions by Yiming Qiu (Rice University), Jiarong Xing (Rice University), Kuo-Feng Hsu (Rice University), Qiao Kang (Rice University), Ming Liu (University of Wisconsin at Madison/VMware Research), Srinivas Narayana (Rutgers University), and Ang Chen (Rice University)

Kauri: Scalable BFT Consensus with Pipelined Tree-Based Dissemination and Aggregation by Ray Neiheiser (INESC-ID, IST, U. Lisboa and UFSC/DAS), Miguel Matos (INESC-ID, IST, U. Lisboa), and Luís Rodrigues (INESC-ID, IST, U. Lisboa)

Mycelium: Large-Scale Distributed Graph Queries with Differential Privacy by Edo Roth (University of Pennsylvania), Karan Newatia (University of Pennsylvania), Yiping Ma (University of Pennsylvania), Ke Zhong (University of Pennsylvania), Sebastian Angel (University of Pennsylvania), and Andreas Haeberlen (University of Pennsylvania)

Coeus: A system for oblivious document ranking and retrieval by Ishtiyaque Ahmad (University of California Santa Barbara), Laboni Sarker (University of California Santa Barbara), Divyakant Agrawal (University of California Santa Barbara), Amr El Abbadi (University of California Santa Barbara), and Trinabh Gupta (University of California Santa Barbara)

PRISM: Rethinking the RDMA Interface for Distributed Systems by Sowmya Dharanipragada (Cornell University), Shannon Joyner (Cornell University), Matthew Burke (Cornell University), Adriana Szekeres (VMWare Research), Jacob Nelson (Microsoft Research), Irene Zhang (Microsoft Research/University of Washington), and Dan Ports (Microsoft Research)

Solving Large-Scale Granular Resource Allocation Problems Efficiently with POP by Deepak Narayanan (Stanford University), Fiodar Kazhamiaka (Stanford University), Firas Abuzaid (Stanford University), Peter Kraft (Stanford University), Akshay Agrawal (Stanford University), Srikanth Kandula (Microsoft Research), Stephen Boyd (Stanford University), and Matei Zaharia (Stanford University and Databricks)

PACTree: A High Performance Persistent Range Index Using PAC Guidelines by Wook-Hee Kim (Virginia Tech), R. Madhava Krishnan (Virginia Tech), Xinwei Fu (Virginia Tech), Sanidhya Kashyap (EPFL), and Changwoo Min (Virginia Tech)

Generating Complex, Realistic Cloud Workloads using Recurrent Neural Networks by Shane Bergsma (Huawei Canada Research Center), Timothy Zeyl (Huawei Canada Research Center), Arik Senderovich (University of Toronto), and J. Christopher Beck (University of Toronto)

Caracal: Contention Management with Deterministic Concurrency Control by Dai Qin (University of Toronto), Angela Demke Brown (University of Toronto), and Ashvin Goel (University of Toronto)

Crash Consistent Non-Volatile Memory Express by Xiaojian Liao (Tsinghua University), Youyou Lu (Tsinghua University), Zhe Yang (Tsinghua University), and Jiwu Shu (Tsinghua University)

FragPicker: A New Defragmentation Tool for Modern Storage Devices by Jonggyu Park (Sungkyunkwan University) and Young Ik Eom (Dept. of Electrical and Computer Engineering/College of Computing and Informatics, Sungkyunkwan University)