NDLI: Broadcast Extensions with Optimal Communication and Round Complexity

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

New Opportunities for PODC?: Massive, Volatile, but Highly Predictable Resources

A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds

Analysing Snapshot Isolation

Deterministic Objects: Life Beyond Consensus

Concurrent Data Structures

Contention Resolution on a Fading Channel

Distributed Strong Diameter Network Decomposition: Extended Abstract

Space Bounds for Reliable Storage: Fundamental Limits of Coding

How Emerging Memory Technologies Will Have You Rethinking Algorithm Design

Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation

A Faster Distributed Radio Broadcast Primitive: Extended Abstract

Search on a Line with Faulty Robots

Low-Congestion Shortcuts without Embedding

The Greedy Spanner is Existentially Optimal

Recoverable Mutual Exclusion: [Extended Abstract]

Unbeatable Set Consensus via Topological and Combinatorial Reasoning

Reliable Communication over Highly Connected Noisy Networks

Optimal Dynamic Distributed MIS

Specification and Complexity of Collaborative Text Editing

On the Complexity of Reader-Writer Locks: Extended Abstract

Broadcast Extensions with Optimal Communication and Round Complexity

Uniform Deployment of Mobile Agents in Asynchronous Rings

The Coalescing-Branching Random Walk on Expanders and the Dual Epidemic Process

MST in Log-Star Rounds of Congested Clique

A Randomized Concurrent Algorithm for Disjoint Set Union

A Polylogarithmic Gossip Algorithm for Plurality Consensus

Contention Resolution on Multiple Channels with Collision Detection

A Local Constant Factor MDS Approximation for Bounded Genus Graphs

Optimal Mobile Byzantine Fault Tolerant Distributed Storage: Extended Abstract

An Algorithm for Replicated Objects with Efficient Reads

Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems

Fault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms

Ant-Inspired Density Estimation via Random Walks: Extended Abstract

Distributed Algorithms for Planar Networks I: Planar Embedding

Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins [Extended Abstract]

Noisy Rumor Spreading and Plurality Consensus

How Asynchrony Affects Rumor Spreading Time

On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract

A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems

Are Shared Objects Composable under an Oblivious Adversary?

How Proofs are Prepared at Camelot: Extended Abstract

Brief Announcement: Active Information Spread in Networks

Brief Announcement: Multi-Broadcasting under the SINR Model

Brief Announcement: Labeling Schemes for Power-Law Graphs

Brief Announcement: Local Independent Set Approximation

Rational Consensus: Extended Abstract

Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Brief Announcement: Deterministic Graph Connectivity in the Broadcast Congested Clique

A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract]

Brief Announcement: A Family of Leaderless Generalized-Consensus Algorithms

Brief Announcement: Proactive Secret Sharing with a Dishonest Majority

Brief Announcement: Certified Universal Gathering in $R^{2}$ for Oblivious Mobile Robots

Brief Announcement: Using Read-k Inequalities to Analyze a Distributed MIS Algorithm

Brief Announcement: Sublinear-Space Distance Labeling Using Hubs

Brief Announcement: A Tight Space Bound for Consensus

Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks

Brief Announcement: Asynchronous Coordination with Constraints and Preferences

Brief Announcement: Computing in the Presence of Weak Crash Failures

Brief Announcement: Probabilistic Asynchronous Arbitrary Pattern Formation

Brief Announcement: A Key-Value Map for Massive Real-Time Analytics

Brief Announcement: Optimal Leader Election in Multi-Hop Radio Networks

Brief Announcement: Reliable Message Transmission under Partial Knowledge and General Adversaries

Brief Announcement: Oh-RAM! One and a Half Round Read/Write Atomic Memory

Brief Announcement: Pattern Formation Problem for Synchronous Mobile Robots in the Three Dimensional Euclidean Space

Brief Announcement: The Small World of Curious Beings

Brief Announcement: Self-stabilizing Clock Synchronization with 3-bit Messages

Brief Announcement: Space-Time Tradeoffs for Distributed Verification

Broadcast Extensions with Optimal Communication and Round Complexity

Content Provider	ACM Digital Library
Author	Patra, Arpita Ganesh, Chaya
Abstract	The problem of broadcast and Byzantine Agreement are of interest to both distributed computing and cryptography community. Often these primitives require prohibitive communication and round complexity. Broadcast extensions have been introduced to broadcast long messages at the cost of small number of broadcasts for bit. The latter are referred to as seed broadcasts. In a setting with n parties and an adversary controlling at most t parties in Byzantine fashion such that t < n, we present a broadcast extension that is simultaneously optimal in terms of communication complexity and round complexity. Specifically, we achieve O(l n) bits of communication complexity for a message of length l bits and O(n) round complexity. The known broadcast extension protocol in the same setting was only communication optimal. A concrete broadcast extension protocol is obtained when the seed broadcasts are instantiated with broadcast protocols for bit. Our optimal broadcast extension protocol in t < n setting leads to concrete extension protocols that improve the round complexity of existing concrete extension protocols by a factor of Ω(n). We also improve the state-of-the-art round complexity of the communication optimal concrete broadcast extension protocol in t < n/2 setting. The result comes as a corollary of a new extension protocol that improves both the round complexity as well as the seed round complexity of the existing extension protocols for t < n/2. The seed round complexity is defined as the number of rounds in which a broadcast for bit is invoked.
Starting Page	371
Ending Page	380
Page Count	10
File Format	PDF
ISBN	9781450339643
DOI	10.1145/2933057.2933082
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-25
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Round complexity Seed round complexity Byzantine agreement Broadcast Communication complexity
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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