ABSTRACT. We present POCS, a concurrency testing approach that directly samples the partial orders of a concurrent program. POCS uses a novel priority-based scheduling algorithm that naturally considers partial order information dynamically, and guarantees that each partial order will be explored with significant probability. This probabilistic guarantee of error detection is exponentially better state-of-the-art sampling approaches. Besides theoretical guarantees, POCS is extremely simple and lightweight to implement. Evaluation shows that POCS is effective in covering the partial-order space of micro-benchmarks and finding concurrency bugs in real-world programs such as Firefox’s JavaScript engine SpiderMonkey