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

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

Résumé

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.

langue originale	Anglais
titre	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
rédacteurs en chef	Jerzy Tiuryn
Editeur	Springer Verlag
Pages	146-160
Nombre de pages	15
ISBN (imprimé)	3540672575, 9783540672579
Les DOIs	https://doi.org/10.1007/3-540-46432-8_10
état	Publié - 1 janv. 2000
Modification externe	Oui
Evénement	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, Allemagne Durée: 25 mars 2000 → 2 avr. 2000

Série de publications

Nom	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1784 LNCS
ISSN (imprimé)	0302-9743
ISSN (Electronique)	1611-3349

Une conférence

Une conférence	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
Pays/Territoire	Allemagne
La ville	Berlin
période	25/03/00 → 2/04/00

Accès au document

10.1007/3-540-46432-8_10

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

Herescu, O. M., & Palamidessi, C. (2000). Probabilistic asynchronous φ-calculus. Dans 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 (p. 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. Editeur / 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)).

@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. Dans 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, p. 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, Allemagne, 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).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

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. Dans Tiuryn J, Editeur, 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

Résumé

Série de publications

Une conférence

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation