ML p(r)ior | Plurality Consensus via Shuffling: Lessons Learned from Load Balancing

Plurality Consensus via Shuffling: Lessons Learned from Load Balancing

2016-02-03
We consider \emph{plurality consensus} in a network of $n$ nodes. Initially, each node has one of $k$ opinions. The nodes execute a (randomized) distributed protocol to agree on the plurality opinion (the opinion initially supported by the most nodes). Nodes in such networks are often quite cheap and simple, and hence one seeks protocols that are not only fast but also simple and space efficient. Typically, protocols depend heavily on the employed communication mechanism, which ranges from sequential (only one pair of nodes communicates at any time) to fully parallel (all nodes communicate with all their neighbors at once) communication and everything in-between. We propose a framework to design protocols for a multitude of communication mechanisms. We introduce protocols that solve the plurality consensus problem and are with probability 1-o(1) both time and space efficient. Our protocols are based on an interesting relationship between plurality consensus and distributed load balancing. This relationship allows us to design protocols that generalize the state of the art for a large range of problem parameters. In particular, we obtain the same bounds as the recent result of Alistarh et al. (who consider only two opinions on a clique) using a much simpler protocol that generalizes naturally to general graphs and multiple opinions.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2019-02-07
1902.02763 | cs.DC

In this paper, we study random gossip processes in communication models that describe the peer-to-pe… show more
PDF

Highlights - Most important sentences from the article

2019-01-07

Motivated by applications in blockchains and sensor networks, we consider a model of $n$ nodes tryin… show more
PDF

Highlights - Most important sentences from the article

2019-04-24

We study a process of \emph{averaging} in a distributed system with \emph{noisy communication}. Each… show more
PDF

Highlights - Most important sentences from the article

2018-11-02
1811.00691 | cs.SY

We consider resilient versions of discrete-time multi-agent consensus in the presence of faulty or e… show more
PDF

Highlights - Most important sentences from the article

2018-05-03

We investigate the behavior of a simple majority dynamics on networks of agents whose interaction to… show more
PDF

Highlights - Most important sentences from the article

2019-01-21

A nonsplit graph is a directed graph where each pair of nodes has a common incoming neighbor. We sho… show more
PDF

Highlights - Most important sentences from the article

2018-07-15

Consensus and Broadcast are two fundamental problems in distributed computing, whose solutions have … show more
PDF

Highlights - Most important sentences from the article

2018-08-16

We consider the following load balancing process for $m$ tokens distributed arbitrarily among $n$ no… show more
PDF

Highlights - Most important sentences from the article

2019-01-02

In this paper, we look at the problem of randomized leader election in synchronous distributed netwo… show more
PDF

Highlights - Most important sentences from the article

2018-12-31

The randomized rumor spreading problem generates a big interest in the area of distributed algorithm… show more
PDF

Highlights - Most important sentences from the article

2018-12-28
1812.10917 | cs.DC

We explore the power of interactive proofs with a distributed verifier. In this setting, the verifie… show more
PDF

Highlights - Most important sentences from the article

2018-05-28
1805.12172 | cs.DS

Assume for a graph $G=(V,E)$ and an initial configuration, where each node is blue or red, in each d… show more
PDF

Highlights - Most important sentences from the article

2012-08-16

The dynamics of an agreement protocol interacting with a disagreement process over a common random n… show more
PDF

Highlights - Most important sentences from the article

2012-08-03

We analyze a class of distributed quantized consen- sus algorithms for arbitrary networks. In the in… show more
PDF

Highlights - Most important sentences from the article

2014-08-22

We study the outcomes of information aggregation in online social networks. Our main result is that … show more
PDF

Highlights - Most important sentences from the article

2017-02-13

We study in-network computation on general network topologies. Specifically, we are given the descri… show more
PDF

Highlights - Most important sentences from the article