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

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

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

Content Provider	ACM Digital Library
Author	Gupta, Anuj Anumanchipalli, Prasant Gopal Bansal, Piyush Srinathan, Kannan Vasishta, Pranav K.
Abstract	Global consistency or Byzantine Agreement (BA) and reliable point-to-point communication are two of the most important and well-studied problems in distributed computing. Informally, BA is about maintaining a consistent view of the world among all the non-faulty players in the presence of faults. In a synchronous network over n nodes of which up to any t are corrupted by a Byzantine adversary, BA is possible only if all pair point-to-point reliable communication is possible [Dol82, DDWY93] Specifically, in the standard unauthenticated model, (2t + 1)-connectivity is necessary whereas in the authenticated setting (t + 1)-connectivity is required. Thus, a folklore is that maintaining global consistency is at least as hard as the problem of all pair point-to-point communication. Equivalently, it is widely believed that protocols for BA over incomplete graphs exist only if it is possible to simulate an overlay-ed complete graph. Surprisingly, we show that the folklore is far from true-- achieving global consistency can be strictly easier than all-pair point-to-point communication. In the authenticated model, it is assumed that the adversary can forge the signatures of only those nodes under its control. In contrast, the unauthenticated model assumes that the adversary can forge the signatures of all the nodes (that is, secure signatures are not used). We initiate a study on the entire gamut of BA's in between, viz., the adversary can forge the signatures of up to any k nodes apart from the up to t nodes that it can actively corrupt. We completely characterize the possibility of BA across the spectrum. Thus, our work attempts to unify the extant literature on agreement. It is, however, more than a mere attempt towards unification as it provides insights into the field. Specifically, apart from the extremes (of k = 0 and k = n − t where aforementioned folklore is known to hold), for every intermediate k, there are several networks over which BA is possible but all-pair point-to-point communication is not.
Starting Page	310
Ending Page	311
Page Count	2
File Format	PDF
ISBN	9781605583969
DOI	10.1145/1582716.1582782
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-08-10
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Agreement Reliable communication Authentication Incomplete 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