Version submitted to ACM TOMPECS