Earlier Version
Cost analysis of nondeterministic probabilistic programs
Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4, Anonymous 5, Anonymous 6. 2018. Cost analysis of nondeterministic probabilistic programs, IST Austria, 27p.
Download
Technical Report
| Published
| English
Scopus indexed
Author
Anonymous, 1;
Anonymous, 2;
Anonymous, 3;
Anonymous, 4;
Anonymous, 5;
Anonymous, 6
Series Title
IST Austria Technical Report
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 by presenting experimental results on a variety of programs, motivated by real-world applications, for which we efficiently synthesize tight resource-usage bounds.
Publishing Year
Date Published
2018-11-11
Publisher
IST Austria
Page
27
ISSN
IST-REx-ID
Cite this
Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4, Anonymous 5, Anonymous 6. Cost Analysis of Nondeterministic Probabilistic Programs. IST Austria; 2018.
Anonymous, 1, Anonymous, 2, Anonymous, 3, Anonymous, 4, Anonymous, 5, & Anonymous, 6. (2018). Cost analysis of nondeterministic probabilistic programs. IST Austria.
Anonymous, 1, 2 Anonymous, 3 Anonymous, 4 Anonymous, 5 Anonymous, and 6 Anonymous. Cost Analysis of Nondeterministic Probabilistic Programs. IST Austria, 2018.
1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, 5 Anonymous, and 6 Anonymous, Cost analysis of nondeterministic probabilistic programs. IST Austria, 2018.
Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4, Anonymous 5, Anonymous 6. 2018. Cost analysis of nondeterministic probabilistic programs, IST Austria, 27p.
Anonymous, 1, et al. Cost Analysis of Nondeterministic Probabilistic Programs. IST Austria, 2018.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
Open Access
Date Uploaded
2018-12-12
MD5 Checksum
ba3adafd36fe200385ccda583063b9eb
File Name
authors-names.txt
322 bytes
Access Level
Closed Access
Date Uploaded
2019-05-10
MD5 Checksum
6cf3a19164bb8e5048a9c8c84dfd9fa3