Randomized distributed decision

Pierre Fraigniaud; Mika Goeoes; Amos Korman; Merav Parter; David Peleg

doi:10.1007/s00446-014-0211-x

Randomized distributed decision

Pierre Fraigniaud, Mika Goeoes, Amos Korman, Merav Parter, David Peleg

Department of Computer Science and Applied Mathematics

Research output: Contribution to journal › Article › peer-review

19 Citations (Scopus)

Abstract

The paper tackles the power of randomization in the context of local distributed computing by analyzing the ability to “boost” the success probability of deciding a distributed language using a Monte-Carlo algorithm. We prove that, in many cases, the ability to increase the success probability for deciding distributed languages is rather limited. This contrasts with the sequential computing setting where boosting can systematically be achieved by repeating the randomized execution.

Original language	English
Pages (from-to)	419-434
Number of pages	16
Journal	Distributed Computing
Volume	27
Issue number	6
DOIs	https://doi.org/10.1007/s00446-014-0211-x
Publication status	Published - 23 Nov 2014

Funding

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Hardware and Architecture
Computer Networks and Communications
Computational Theory and Mathematics

Access to Document

10.1007/s00446-014-0211-x

Cite this

@article{bf459a4735334e32bff9556068224055,

title = "Randomized distributed decision",

abstract = "The paper tackles the power of randomization in the context of local distributed computing by analyzing the ability to “boost” the success probability of deciding a distributed language using a Monte-Carlo algorithm. We prove that, in many cases, the ability to increase the success probability for deciding distributed languages is rather limited. This contrasts with the sequential computing setting where boosting can systematically be achieved by repeating the randomized execution.",

author = "Pierre Fraigniaud and Mika Goeoes and Amos Korman and Merav Parter and David Peleg",

year = "2014",

month = nov,

day = "23",

doi = "10.1007/s00446-014-0211-x",

language = "English",

volume = "27",

pages = "419--434",

journal = "Distributed Computing",

issn = "0178-2770",

publisher = "Springer Verlag",

number = "6",

}

TY - JOUR

T1 - Randomized distributed decision

AU - Fraigniaud, Pierre

AU - Goeoes, Mika

AU - Korman, Amos

AU - Parter, Merav

AU - Peleg, David

PY - 2014/11/23

Y1 - 2014/11/23

N2 - The paper tackles the power of randomization in the context of local distributed computing by analyzing the ability to “boost” the success probability of deciding a distributed language using a Monte-Carlo algorithm. We prove that, in many cases, the ability to increase the success probability for deciding distributed languages is rather limited. This contrasts with the sequential computing setting where boosting can systematically be achieved by repeating the randomized execution.

AB - The paper tackles the power of randomization in the context of local distributed computing by analyzing the ability to “boost” the success probability of deciding a distributed language using a Monte-Carlo algorithm. We prove that, in many cases, the ability to increase the success probability for deciding distributed languages is rather limited. This contrasts with the sequential computing setting where boosting can systematically be achieved by repeating the randomized execution.

UR - http://www.scopus.com/inward/record.url?scp=84912014973&partnerID=8YFLogxK

U2 - 10.1007/s00446-014-0211-x

DO - 10.1007/s00446-014-0211-x

M3 - Article

SN - 0178-2770

VL - 27

SP - 419

EP - 434

JO - Distributed Computing

JF - Distributed Computing

IS - 6

ER -

Randomized distributed decision

Abstract

Funding

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this