NDLI: Simple and efficient asynchronous byzantine agreement with optimal resilience

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

The life and times of a zookeeper

Preventing versus curing: avoiding conflicts in transactional memories

Tight bounds for clock synchronization

The weakest failure detector for solving k-set agreement

The forgiving graph: a distributed data structure for low stretch under adversarial attack

Fast distributed random walks

The wireless synchronization problem

Efficient broadcasting in known topology radio networks with long-range interference

Brief announcement: Stateless distributed algorithms for generalized packing linear programs

Brief announcement: a note on distributed stable matching

Brief announcement: the price of anonymity: optimal consensus despite asynchrony, crash and anonymity

Brief announcement: PUSH, a DISC shell

Brief announcement: the theory of network tracing

Brief announcement: hardness of broadcasting in wireless networks with unreliable communication

Refining the way to consensus

Cassandra: structured storage system on a P2P network

Dynamic atomic storage without consensus

Load balancing without regret in the bulletin board model

Simple and efficient asynchronous byzantine agreement with optimal resilience

A distributed polylogarithmic time algorithm for self-stabilizing skip graphs

Distributed and parallel algorithms for weighted vertex cover and other covering problems

SINR diagrams: towards algorithmically usable SINR models of wireless networks

The effect of power-law degrees on the navigability of small worlds: [extended abstract]

Brief announcement: concurrent non-commutative boosted transactions

On a selfish caching game

Brief announcement: minimum spanning trees and cone-based topology control

Brief announcement: deaf, dumb, and chatting robots

Brief announcement: (more) efficient pruning of ad-hoc wireless networks

Brief announcement: complexity analysis and algorithm design for pipeline configuration in distributed networks

Memory models: a case for rethinking parallel languages and hardware

Pregel: a system for large-scale graph processing - "ABSTRACT"

Randomized mutual exclusion in O(log N / log log N) RMRs

Concurrent imitation dynamics in congestion games

Partial synchrony based on set timeliness

The flip markov chain and a randomising P2P protocol

Return of the primal-dual: distributed metric facilitylocation

Coloring unstructured wireless multi-hop networks

Bounding the locality of distributed routing algorithms

Brief announcement: distributed phase synchronization of dynamic set of processes

Brief announcement: non-self-stabilizing and self-stabilizing gathering in networks of mobile agents--the notion of speed

Brief announcement: locality-based aggregate computation in wireless sensor networks

Brief announcement: global consistency can be easier than point-to-point communication

Brief announcement: self-assembly as graph grammar as distributed system

Brief announcement: exactly electing a unique leader is not harder than computing symmetric functions on anonymous quantum networks

Emerging challenges and opportunities in parallel computing: the cretaceous redux?

Max registers, counters, and monotone circuits

Extracting quorum failure detectors

Fast scalable deterministic consensus for crash failures

Correctness of gossip-based membership under message loss

Oblivious interference scheduling

Parsimonious flooding in dynamic graphs

Brief announcement: how to speed-up fault-tolerant clock generation in VLSI systems-on-chip via pipelining

The disagreement power of an adversary: extended abstract

Brief announcement: tight lower bounds for greedy routing in uniform small world rings

Vertical paxos and primary-backup replication

Distributed discovery of large near-cliques

Brief announcement: impossibility results for optimistic fair exchange with multiple autonomous arbiters

Brief announcement: perfectly secure message transmission in directed networks re-visited

Brief announcement: weakest failure detectors via an egg-laying simulation

Brief announcement: optimal self-stabilizing multi-token ring: a randomized solution

Brief announcement: topology knowledge affects probabilistic reliable communication

Brief announcement: lightweight key agreement and digital certificates for wireless sensor networks

Brief announcement: collaborative measurement of upload speeds in P2P systems

Brief announcement: virtual world consistency: a new condition for STM systems

Brief announcement: optimization based rate allocation for application layer multicast

Brief announcement: fast scalable Byzantine agreement in the full information model with a nonadaptive adversary

Brief announcement: a platform for experimenting with mobile algorithms in a laboratory

Brief announcement: distributed algorithms for approximating wireless network capacity

Brief announcement: new bounds for the controller problem

Simple and efficient asynchronous byzantine agreement with optimal resilience

Content Provider	ACM Digital Library
Author	Patra, Arpita Choudhary, Ashish Pandu Rangan, Chandrasekharan
Abstract	Consider a completely asynchronous network consisting of n parties where every two parties are connected by a private channel. An adversary $A_{t}$ with unbounded computing power actively controls at most t = ([n/3] − 1) out of n parties in Byzantine fashion. In this setting, we say that π is a t-resilient, (1 − ε)-terminating Asynchronous Byzantine Agreement (ABA) protocol, if π satisfies all the properties of Byzantine Agreement (BA) in asynchronous settings tolerating $A_{t}$ and terminates (i.e every honest party terminates π with probability at least (1 − ε). In this work, we present a new t-resilient, (1 − ε)-terminating ABA protocol which privately communicates $O(Cn^{6}$ κ) bits and $A-casts^{1}$ $O(Cn^{6}$ κ) bits, where ε = $2^{−Ω(κ)}$ and C is the expected running time of the protocol. Moreover, conditioned on the event that our ABA protocol terminates, it does so in constant expected time; i.e., C = O(1). Our ABA protocol is to be compared with the only known t-resilient, (1 − ε)-terminating ABA protocol of [5] in the same settings, which privately communicates $O(Cn^{11}$ $κ^{4})$ bits and A-casts $O(Cn^{11}$ $κ^{2}$ log(n)) bits, where ε = $2^{−Ω(κ)}$ and C = O(1). So our ABA achieves a huge gain in communication complexity in comparison to the ABA of [5], while keeping all other properties in place. In another landmark work, in PODC 2008, Abraham et. al [1] proposed a t-resilient, 1-terminating (called as almost-surely terminating in [1]) ABA protocol which privately communicates $O(Cn^{6}$ log n) bits and A-casts $O(Cn^{6}$ log n) bits. But ABA protocol of Abraham et. al. takes polynomial (C = $O(n^{2}))$ expected time to terminate. Hence the merits of our ABA protocol over the ABA of Abraham et. al. are: (i) For any κ < $n^{2}$ log n, our ABA is better in terms of communication complexity (ii) conditioned on the event that our ABA protocol terminates, it does so in constant expected time (the constant is independent of n, t and κ), whereas ABA of Abraham et. al. takes polynomial expected time. Summing up, in a practical scenario where a faster and communication efficient ABA protocol is required, our ABA fits the bill better than ABA protocols of [5, 1]. For designing our ABA protocol, we present a novel and simple asynchronous verifiable secret sharing (AVSS) protocol which significantly improves the communication complexity of the only known AVSS protocol of [5] in the same settings. We believe that our AVSS can be used in many other applications for improving communication complexity and hence is of independent interest.
Starting Page	92
Ending Page	101
Page Count	10
File Format	PDF
ISBN	9781605583969
DOI	10.1145/1582716.1582736
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-08-10
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Byzantine agreement Vss Unbounded computing power Asynchronous networks
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