Cost analysis of nondeterministic probabilistic programs

P. Wang, H. Fu, A.K. Goharshady, K. Chatterjee, X. Qin, W. Shi, in:, 40th ACM Conference on Programming Language Design and Implementation (PLDI 2019), Association for Computing Machinery, 2019, pp. 204–220.

Download
OA 4.05 MB

Conference Paper | Published | English
Author
Department
Abstract
We consider the problem of expected cost analysis over nondeterministic probabilistic programs, which aims at automated methods for analyzing the resource-usage of such programs. Previous approaches for this problem could only handle nonnegative bounded costs. However, in many scenarios, such as queuing networks or analysis of cryptocurrency protocols, both positive and negative costs are necessary and the costs are unbounded as well. In this work, we present a sound and efficient approach to obtain polynomial bounds on the expected accumulated cost of nondeterministic probabilistic programs. Our approach can handle (a) general positive and negative costs with bounded updates in variables; and (b) nonnegative costs with general updates to variables. We show that several natural examples which could not be handled by previous approaches are captured in our framework. Moreover, our approach leads to an efficient polynomial-time algorithm, while no previous approach for cost analysis of probabilistic programs could guarantee polynomial runtime. Finally, we show the effectiveness of our approach using experimental results on a variety of programs for which we efficiently synthesize tight resource-usage bounds.
Publishing Year
Date Published
2019-06-08
Proceedings Title
40th ACM Conference on Programming Language Design and Implementation (PLDI 2019)
Page
204-220
Conference
40th ACM Conference on Programming Language Design and Implementation
Conference Location
Phoenix, AZ, United States
Conference Date
2019-06-22 – 2019-06-26
IST-REx-ID

Cite this

Wang P, Fu H, Goharshady AK, Chatterjee K, Qin X, Shi W. Cost analysis of nondeterministic probabilistic programs. In: 40th ACM Conference on Programming Language Design and Implementation (PLDI 2019). Association for Computing Machinery; 2019:204-220. doi:10.1145/3314221.3314581
Wang, P., Fu, H., Goharshady, A. K., Chatterjee, K., Qin, X., & Shi, W. (2019). Cost analysis of nondeterministic probabilistic programs. In 40th ACM Conference on Programming Language Design and Implementation (PLDI 2019) (pp. 204–220). Phoenix, AZ, United States: Association for Computing Machinery. https://doi.org/10.1145/3314221.3314581
Wang, Peixin, Hongfei Fu, Amir Kafshdar Goharshady, Krishnendu Chatterjee, Xudong Qin, and Wenjun Shi. “Cost Analysis of Nondeterministic Probabilistic Programs.” In 40th ACM Conference on Programming Language Design and Implementation (PLDI 2019), 204–20. Association for Computing Machinery, 2019. https://doi.org/10.1145/3314221.3314581.
P. Wang, H. Fu, A. K. Goharshady, K. Chatterjee, X. Qin, and W. Shi, “Cost analysis of nondeterministic probabilistic programs,” in 40th ACM Conference on Programming Language Design and Implementation (PLDI 2019), Phoenix, AZ, United States, 2019, pp. 204–220.
Wang P, Fu H, Goharshady AK, Chatterjee K, Qin X, Shi W. 2019. Cost analysis of nondeterministic probabilistic programs. 40th ACM Conference on Programming Language Design and Implementation (PLDI 2019). 40th ACM Conference on Programming Language Design and Implementation 204–220.
Wang, Peixin, et al. “Cost Analysis of Nondeterministic Probabilistic Programs.” 40th ACM Conference on Programming Language Design and Implementation (PLDI 2019), Association for Computing Machinery, 2019, pp. 204–20, doi:10.1145/3314221.3314581.
Main File(s)
File Name
4.05 MB
Access Level
OA Open Access
Last Uploaded
2019-03-25T10:11:22Z


Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1902.04659

Search this title in

Google Scholar