Probabilistic asynchronous φ-calculus

Oltea Mihaela Herescu; Catuscia Palamidessi

doi:10.1007/3-540-46432-8_10

Probabilistic asynchronous φ-calculus

Oltea Mihaela Herescu
, Catuscia Palamidessi

Penn State University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We propose an extension of the asynchronous φ-calculus with a notion of random choice. We define an operational semantics which distinguishes between probabilistic choice, made internally by the process, and nondeterministic choice, made externally by an adversary scheduler. This distinction will allow us to reason about the probabilistic correctness of algorithms under certain schedulers. We show that in this language we can solve the electoral problem, which was proved not possible in the asynchronous φ-calculus. Finally, we show an implementation of the probabilistic asynchronous φ-calculus in a Java-like language.

Original language	English
Title of host publication	Foundations of Software Science and Computation Structures - Third International Conference, FOSSACS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000
Editors	Jerzy Tiuryn
Publisher	Springer Verlag
Pages	146-160
Number of pages	15
ISBN (Print)	3540672575, 9783540672579
DOIs	https://doi.org/10.1007/3-540-46432-8_10
Publication status	Published - 1 Jan 2000
Externally published	Yes
Event	3rd International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000 - Berlin, Germany Duration: 25 Mar 2000 → 2 Apr 2000

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1784 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000
Country/Territory	Germany
City	Berlin
Period	25/03/00 → 2/04/00

Access to Document

10.1007/3-540-46432-8_10

Cite this

Herescu, O. M., & Palamidessi, C. (2000). Probabilistic asynchronous φ-calculus. In J. Tiuryn (Ed.), Foundations of Software Science and Computation Structures - Third International Conference, FOSSACS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000 (pp. 146-160). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1784 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-46432-8_10

Herescu, Oltea Mihaela ; Palamidessi, Catuscia. / Probabilistic asynchronous φ-calculus. Foundations of Software Science and Computation Structures - Third International Conference, FOSSACS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000. editor / Jerzy Tiuryn. Springer Verlag, 2000. pp. 146-160 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ac88ab8135774377a345b23af9b17605,

title = "Probabilistic asynchronous φ-calculus",

abstract = "We propose an extension of the asynchronous φ-calculus with a notion of random choice. We define an operational semantics which distinguishes between probabilistic choice, made internally by the process, and nondeterministic choice, made externally by an adversary scheduler. This distinction will allow us to reason about the probabilistic correctness of algorithms under certain schedulers. We show that in this language we can solve the electoral problem, which was proved not possible in the asynchronous φ-calculus. Finally, we show an implementation of the probabilistic asynchronous φ-calculus in a Java-like language.",

author = "Herescu, \{Oltea Mihaela\} and Catuscia Palamidessi",

year = "2000",

month = jan,

day = "1",

doi = "10.1007/3-540-46432-8\_10",

language = "English",

isbn = "3540672575",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "146--160",

editor = "Jerzy Tiuryn",

booktitle = "Foundations of Software Science and Computation Structures - Third International Conference, FOSSACS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000",

note = "3rd International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000 ; Conference date: 25-03-2000 Through 02-04-2000",

}

Herescu, OM & Palamidessi, C 2000, Probabilistic asynchronous φ-calculus. in J Tiuryn (ed.), Foundations of Software Science and Computation Structures - Third International Conference, FOSSACS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1784 LNCS, Springer Verlag, pp. 146-160, 3rd International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000, Berlin, Germany, 25/03/00. https://doi.org/10.1007/3-540-46432-8_10

Probabilistic asynchronous φ-calculus. / Herescu, Oltea Mihaela; Palamidessi, Catuscia.
Foundations of Software Science and Computation Structures - Third International Conference, FOSSACS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000. ed. / Jerzy Tiuryn. Springer Verlag, 2000. p. 146-160 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1784 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Probabilistic asynchronous φ-calculus

AU - Herescu, Oltea Mihaela

AU - Palamidessi, Catuscia

PY - 2000/1/1

Y1 - 2000/1/1

N2 - We propose an extension of the asynchronous φ-calculus with a notion of random choice. We define an operational semantics which distinguishes between probabilistic choice, made internally by the process, and nondeterministic choice, made externally by an adversary scheduler. This distinction will allow us to reason about the probabilistic correctness of algorithms under certain schedulers. We show that in this language we can solve the electoral problem, which was proved not possible in the asynchronous φ-calculus. Finally, we show an implementation of the probabilistic asynchronous φ-calculus in a Java-like language.

AB - We propose an extension of the asynchronous φ-calculus with a notion of random choice. We define an operational semantics which distinguishes between probabilistic choice, made internally by the process, and nondeterministic choice, made externally by an adversary scheduler. This distinction will allow us to reason about the probabilistic correctness of algorithms under certain schedulers. We show that in this language we can solve the electoral problem, which was proved not possible in the asynchronous φ-calculus. Finally, we show an implementation of the probabilistic asynchronous φ-calculus in a Java-like language.

UR - https://www.scopus.com/pages/publications/84878650387

U2 - 10.1007/3-540-46432-8_10

DO - 10.1007/3-540-46432-8_10

M3 - Conference contribution

AN - SCOPUS:84878650387

SN - 3540672575

SN - 9783540672579

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 146

EP - 160

BT - Foundations of Software Science and Computation Structures - Third International Conference, FOSSACS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000

A2 - Tiuryn, Jerzy

PB - Springer Verlag

T2 - 3rd International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000

Y2 - 25 March 2000 through 2 April 2000

ER -

Herescu OM, Palamidessi C. Probabilistic asynchronous φ-calculus. In Tiuryn J, editor, Foundations of Software Science and Computation Structures - Third International Conference, FOSSACS 2000, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000. Springer Verlag. 2000. p. 146-160. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-46432-8_10

Probabilistic asynchronous φ-calculus

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this