4 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…
Lower Bounds for -Set Agreement in Fault-Prone Networks
Pierre Fraigniaud, Minh Hang Nguyen, Ami Paz +2
We develop a new lower bound for k-set agreement in synchronous message-passing systems connected by an arbitrary directed communication network, where up to t processes may crash.…
Semi-Streaming Algorithms for Graph Property Certification
Avinandan Das, Pierre Fraigniaud, Ami Paz +1
We introduce the {\em certification} of solutions to graph problems when access to the input is restricted. This topic has received a lot of attention in the distributed computing…
A Simple Lower Bound for Set Agreement in Dynamic Networks
Pierre Fraigniaud, Minh Hang Nguyen, Ami Paz
Given a positive integer , -set agreement is the distributed task in which each process in a group of processing nodes starts with an input value in the…