NDLI: Brief Announcement: Rapid Asynchronous Plurality Consensus

Please wait, while we are loading the content...

Some Sequential Algorithms are Almost Always Parallel

Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks

Analyzing Contention and Backoff in Asynchronous Shared Memory

LCL Problems on Grids

Blockchains and the Future of Distributed Computing

A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities

Recoverable Mutual Exclusion in Sub-logarithmic Time

Effectiveness of Delaying Timestamp Computation

Verifiable Outsourced Computation: A Survey

FruitChains: A Fair Blockchain

Greedy Routing and the Algorithmic Small-World Phenomenon

Towards Efficient Verification of Population Protocols

The Space Requirement of Local Forwarding on Acyclic Networks

A Layered Architecture for Erasure-Coded Consistent Distributed Storage

On the Multiparty Communication Complexity of Testing Triangle-Freeness

Distributed Approximation of Maximum Independent Set and Maximum Matching

Randomized Abortable Mutual Exclusion with Constant Amortized RMR Complexity on the CC Model

Symmetry Breaking with Noisy Processes

Coordination Without Prior Agreement

Triangle Finding and Listing in CONGEST Networks

Clocked Population Protocols

Communication Primitives in Cognitive Radio Networks

Seeing is Believing: A Client-Centric Specification of Database Isolation

What Can be Sampled Locally?

Deterministic Distributed (Delta + o(Delta))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity

Transactional Lock Elision Meets Combining

The Power of Choice in Priority Scheduling

Ignore or Comply?: On Breaking Symmetry in Consensus

Asynchronous Shared Channel

A Distributed Learning Dynamics in Social Groups

Broadcasting in Noisy Radio Networks

Space Complexity of Fault-Tolerant Register Emulations

Distributed MST and Routing in Almost Mixing Time

Optimal Distance Labeling Schemes for Trees

On Using Time Without Clocks via Zigzag Causality

A Template for Implementing Fast Lock-free Trees Using HTM

Life Beyond Set Agreement

Self-organized Segregation on the Grid

Brief Announcement: Population Protocols for Leader Election and Exact Majority with $O(log^{2}$ n) States and $O(log^{2}$ n) Convergence Time

Gossip in a Smartphone Peer-to-Peer Network

Brief Announcement: Readers of Wait-Free Unbounded Registers Must Write

Distributed MIS via All-to-All Communication

Brief Announcement: How Large is your Graph?

Brief Announcement: Proust: A Design Space for Highly-Concurrent Transactional Data Structures

Adding Concurrency to Smart Contracts

Brief Announcement: Hierarchical Consensus

Brief Announcement: Efficient Self-Stabilizing 1-Maximal Matching Algorithm for Arbitrary Networks

Brief Announcement: Byzantine-Tolerant Machine Learning

Brief Announcement: Fast Shared Counting using (O(n)) Compare-and-Swap Registers

Brief Announcement: Optimal Address-Oblivious Epidemic Dissemination

Brief Announcement: Distributed Approximation for Tree Augmentation

Brief Announcement: Gossiping with Latencies

Brief Announcement: Statement Voting and Liquid Democracy

Brief Announcement: Secure Self-Stabilizing Computation

Brief Announcement: Certified Multiplicative Weights Update: Verified Learning Without Regret

Brief Announcement: Fence Insertion for Straight-line Programs is in P

Brief Announcement: Leader Election in SINR Model with Arbitrary Power Control

Brief Announcement: A Probabilistic Performance Model and Tuning Framework for Eventually Consistent Distributed Storage Systems

Brief Announcement: Rapid Asynchronous Plurality Consensus

Stateless Computation

Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets

Brief Announcement: Object Oriented Consensus

Brief Announcement: Rapid Asynchronous Plurality Consensus

Content Provider	ACM Digital Library
Author	Trinker, Horst Elsässer, Robert Kaaser, Dominik Friedetzky, Tom Mallmann-Trenn, Frederik
Abstract	We consider distributed plurality consensus on a complete graph of size n with k initial opinions in the following asynchronous communication model. Each node is equipped with a random Poisson clock with parameter lambda=1. Whenever a node's clock ticks, it samples some neighbors uniformly at random and adjusts its opinion according to the sample. Distributed plurality consensus has been deeply studied in the synchronous communication model. A prominent example is the so-called Two-Choices protocol, where in each round, every node chooses two neighbors uniformly at random, and if the two sampled opinions coincide, then that opinion is adopted. This protocol is very efficient when k=2. If $k=O(n^{ε})$ for some small epsilon, we show that it converges to the initial plurality opinion within O(k log n) rounds, w.h.p., as long as the initial difference between the largest and second largest opinion is Omega(sqrt(n log n)). On the negative side, we show that there are cases in which Omega(k) rounds are needed, w.h.p. To beat this lower bound, we combine the Two-Choices protocol with push-pull broadcasting. We divide the process into several phases, where each phase consists of a two-choices round followed by several broadcasting rounds. Our main contribution is a non-trivial adaptation of this approach to the above asynchronous model. If the support of the most frequent opinion is at least (1+ε) times that of the second-most frequent one and k=O(Exp(log n / log log n)), then our protocol achieves the best possible run time of O(log n), w.h.p. Key to our adaptation is that we relax full synchronicity by allowing o(n) nodes to be poorly synchronized, and the well synchronized nodes are only required to be within a certain time difference from one another. We enforce this sufficient synchronicity by introducing a novel gadget into the protocol. Other parts of the adaptation are made to work using arguments and techniques based on a Pólya urn model.
Starting Page	363
Ending Page	365
Page Count	3
File Format	PDF
ISBN	9781450349925
DOI	10.1145/3087801.3087860
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-07-25
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Distributed randomized algorithms Plurality consensus Asynchronicity
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Brief Announcement: Object Oriented Consensus

Brief announcement: a leader-free byzantine consensus algorithm.

Brief announcement: byzantine agreement with a strong adversary in polynomial expected time

Brief Announcement: A Family of Leaderless Generalized-Consensus Algorithms

Rapid Asynchronous Plurality Consensus

Simple dynamics for plurality consensus

Rapid Asynchronous Plurality Consensus

Wait-Free Consensus Using Asynchronous Hardware

Brief announcement: distributed universality: contention-awareness; wait-freedom; object progress, and other properties

Brief Announcement: Rapid Asynchronous Plurality Consensus

Similar Documents

Brief Announcement: Object Oriented Consensus

Brief announcement: a leader-free byzantine consensus algorithm.

Brief announcement: byzantine agreement with a strong adversary in polynomial expected time

Brief Announcement: A Family of Leaderless Generalized-Consensus Algorithms

Rapid Asynchronous Plurality Consensus

Simple dynamics for plurality consensus

Rapid Asynchronous Plurality Consensus

Wait-Free Consensus Using Asynchronous Hardware

Brief announcement: distributed universality: contention-awareness; wait-freedom; object progress, and other properties

Brief Announcement: Rapid Asynchronous Plurality Consensus