5 citations · 20 across the 12 of their papers we have counts for
7 papers · 1 filter
Consensus with Stochastic Broadcast
Pierre Fraigniaud, Boaz Patt-Shamir, Sergio Rajsbaum
We study binary consensus in the \emph{stochastic broadcast model}, which assumes processes communicating synchronously by message broadcasts. At each round, every proces…
Distributed Computing With the Cloud
Yehuda Afek, Gal Giladi, Boaz Patt-Shamir
We investigate the effect of omnipresent cloud storage on distributed computing. We specify a network model with links of prescribed bandwidth that connect standard processing node…
Proof-Labeling Schemes: Broadcast, Unicast and In Between
Boaz Patt-Shamir, Mor Perry
We study the effect of limiting the number of different messages a node can transmit simultaneously on the verification complexity of proof-labeling schemes (PLS). In a PLS, each n…
Buffer Size for Routing Limited-Rate Adversarial Traffic
Avery Miller, Boaz Patt-Shamir
We consider the slight variation of the adversarial queuing theory model, in which an adversary injects packets with routes into the network subject to the following constraint: Fo…
Fast Partial Distance Estimation and Applications
Christoph Lenzen, Boaz Patt-Shamir
We study approximate distributed solutions to the weighted {\it all-pairs-shortest-paths} (APSP) problem in the CONGEST model. We obtain the following results. A deterministic…
Improved Distributed Steiner Forest Construction
Christoph Lenzen, Boaz Patt-Shamir
We present new distributed algorithms for constructing a Steiner Forest in the CONGEST model. Our deterministic algorithm finds, for any given constant , a -approximati…