NDLI: Wait-freedom with advice

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

Faster randomized consensus with an oblivious adversary

Random walks which prefer unvisited edges.: exploring high girth even degree expanders in linear time.

The cost of fault tolerance in multi-party communication complexity

Brief announcement: what can be computed without communication?

Wait-freedom with advice

Distributed selfish load balancing with weights and speeds

Distributed maximal matching: greedy is optimal

Aggregation in dynamic networks

Brief announcement: achieving reliability in master-worker computing via evolutionary dynamics

Asynchronous failure detectors

A simple approach for adapting continuous load balancing processes to discrete settings

On the (limited) power of non-equivocation

Brief announcement: network formation games can give rise to realistic networks

Distributed algorithms for scheduling on line and tree networks

Faster than optimal snapshots (for a while): preliminary version

On the liveness of transactional memory

Information spreading in dynamic graphs

The communication complexity of distributed task allocation

Brief announcement: distributed algorithms for throughput performance in wireless networks

Universal constructions that ensure disjoint-access parallelism and wait-freedom

Making evildoers pay: resource-competitive broadcast in sensor networks

Lower bounds for local approximation

Distributed connectivity of wireless networks

Brief announcement: breaking the O(nm) bit barrier, secure multiparty computation with a static adversary

Simulations and reductions for colorless tasks

Dynamic packet scheduling in wireless networks

On the price of equivocation in byzantine agreement

Brief announcement: network-destabilizing attacks

Optimal distributed all pairs shortest paths and applications

Strongly linearizable implementations: possibilities and impossibilities

On the time and space complexity of randomized test-and-set

Coalescing random walks and voting on graphs

Collaborative search on the plane without communication

Brief announcement: distributed cryptography using trinc

Generalized lattice agreement

Distributed public key schemes secure against continual leakage

Weak models of distributed computing, with connections to modal logic

Leader election in shared spectrum radio networks

Brief announcement: maintaining large dense subgraphs on dynamic networks

A closer look at fault tolerance

Competitive and fair throughput for co-existing networks under adversarial interference

Byzantine broadcast in point-to-point networks using local linear coding

Brief announcement: tolerating permanent and transient value faults

Iterative approximate byzantine consensus in arbitrary directed graphs

Brief announcement: reconfigurable state machine replication from non-reconfigurable building blocks

Brief announcement: decentralized network supercomputing in the presence of malicious and crash-prone workers

Brief announcement: efficient causality tracking in distributed storage systems with dotted version vectors

Brief announcement: all-to-all gradecast using coding with byzantine failures

Brief announcement: order-preserving renaming in synchronous message passing systems with byzantine faults

Brief announcement: increasing the power of the iterated immediate snapshot model with failure detectors

Brief announcement: there are plenty of tasks weaker than perfect renaming and stronger than set agreement

Brief announcement: an obstacle to scalability in wireless networks

Brief announcement: delay or deliver dilemma in organization networks

Brief announcement: waiting in dynamic networks

Brief announcement: on the resilience of routing tables

Brief announcement: live streaming with utilities, quality and cost

Brief announcement: optimal amortized secret sharing with cheater identification

Brief announcement: a tight RMR lower bound for randomized mutual exclusion

Brief announcement: a calculus of policy-based routing systems

Brief announcement: efficient optimally resilient statistical AVSS and its applications

Brief announcement: From sequential to concurrent: correctness and relative efficiency

Wait-freedom with advice

Content Provider	ACM Digital Library
Author	Kuznetsov, Petr Gafni, Eli Fauconnier, Hugues Delporte-Gallet, Carole
Abstract	We motivate and propose a new way of thinking about failure detectors which allows us to define, quite surprisingly, what it means to solve a distributed task wait-free using a failure detector. In our model, the system is composed of computation processes that obtain inputs and are supposed to produce outputs and synchronization processes that are subject to failures and can query a failure detector. Under the condition that correct synchronization processes take sufficiently many steps, they provide the computation processes with enough advice to solve the given task wait-free: every computation process outputs in a finite number of its own steps, regardless of the behavior of other computation processes. Every task can thus be characterized by the weakest failure detector that allows for solving it, and we show that every such failure detector captures a form of set agreement. We then obtain a complete classification of tasks, including ones that evaded comprehensible characterization so far, such as renaming or weak symmetry breaking.
Starting Page	105
Ending Page	114
Page Count	10
File Format	PDF
ISBN	9781450314503
DOI	10.1145/2332432.2332456
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-07-16
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Failure detectors Wait-freedom Computation and synchronization
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