5 citations · 20 across the 12 of their papers we have counts for
16 papers
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…
Colorful Vertex Recoloring of Bipartite Graphs
Boaz Patt-Shamir, Adi Rosen, Seeun William Umboh
In vertex recoloring, we are given vertices with their initial coloring, and edges arrive in an online fashion. The algorithm must maintain a valid coloring by recoloring verti…
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…
With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing
Avery Miller, Boaz Patt-Shamir, Will Rosenbaum
We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate and burstiness . In this model, we analyze th…
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…