NDLI: Lower bounds for adaptive collect and related objects

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

Completely fair SFE and coalition-safe cheap talk

Bringing practical lock-free synchronization to 64-bit applications

Lock-free linked lists and skip lists

On the inherent weakness of conditional synchronization primitives

Load balancing and locality in range-queriable data structures

Compact routing on euclidian metrics

Eclecticism shrinks even small worlds

Balanced binary trees for ID management and load balance in distributed hash tables

Byzantine disk paxos: optimal resilience with byzantine shared memory

Competitive on-line paging strategies for mobile users under delay constraints

A note on efficient aggregate queries in sensor networks

Geometrically aware communication in random wireless networks

Gradient clock synchronization

The weakest failure detectors to solve certain fundamental problems in distributed computing

Brief announcement: stretch between nearby peers

Brief announcement: a single enqueuer wait-free queue implementation

Brief announcement: exposing and eliminating vulnerabilities to denial of service attacks in secure gossip-based multicast

Brief announcement: self-stabilizing distance-d distinct labels via enriched fair composition

Brief announcement: randomized rumor spreading with fewer phone calls

Brief announcement: towards a secure indirection infrastructure

Brief announcement: reconfigurable byzantine-fault-tolerant atomic memory

Brief announcement: polygonal broadcast, secret maturity and the firing sensors

Brief announcement: RT oblivious erasure correcting

Brief announcement: degree: optimal deterministic routing for P2P systems

Brief announcement: on the round complexity of distributed consensus over synchronous networks

Brief announcement: the synchronous condition-based consensus hierarchy

Brief announcement: on the inherent cost of generic broadcast

Mechanism design for policy routing

An almost non-blocking stack

Lower bounds for adaptive collect and related objects

Specification faithfulness in networks with rational nodes

Choosing a random peer

When graph theory helps self-stabilization

Analyzing Kleinberg's (and other) small-world Models

Efficient top-K query calculation in distributed networks

How fast can a distributed atomic read be?

A better wake-up in radio networks

Computation in networks of passively mobile finite-state sensors

Communication-efficient leader election and consensus with limited link synchrony

Group membership: a novel approach and the first single-round algorithm

Brief announcement: prefix hash tree

Brief Announcement: constraint-based synchronization and verification of concurrent programs

Brief announcement: spoofing prevention method

Brief announcement: STALK: a self-stabilizing hierarchical tracking service for sensor networks

Brief announcement: an incremental algorithm for calculation of backup-paths in link-state networks

Brief announcement: Trilix: a scalable unstructured lookup system for dynamic environments

Brief announcement: adaptive balancing networks

Brief announcement: optimal asynchronous garbage collection for checkpointing protocols with rollback-dependency trackability

Brief announcement: secret handshakes from CA-oblivious encryption

Brief announcement: efficient clustering in unstructured radio networks

Brief announcement: veto number and the respective power of eventual failure detectors

Brief announcement: efficient implementation of a byzantine data storage system

Brief announcement: on the possibility of consensus in asynchronous systems with finite average response times

Selfish caching in distributed systems: a game-theoretic analysis

Efficient synchronous snapshots

On the expected payment of mechanisms for task allocation

Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game

Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models

Tradeoffs between stretch factor and load balancing ratio in routing on growth restricted graphs

On the design of distributed protocols from differential equations

Signed quorum systems

Broadcast in radio networks tolerating byzantine adversarial behavior

What cannot be computed locally!

Asynchronous group key exchange with failures

Brief announcement: detecting malicious routers

Brief announcement: completing the lock-free dynamic cycle

Brief announcement: concurrent maintenance of rings

Brief announcement: linear time byzantine self-stabilizing clock synchronization

Brief announcement: name-independent compact routing in trees

Brief announcement: virtual mobile nodes for mobile ad hoc networks

Brief announcement: building an adaptive distributed web server system on the fly for handling web hotspots

On spectrum sharing games

Brief announcement: implementing multi-word atomic snapshots on current hardware

Brief announcement: the design of an internet-scale monitoring and assertion-checking infrastructure

Brief announcement: Cataclysm: handling extreme overloads in internet services

Lower bounds for adaptive collect and related objects

Content Provider	ACM Digital Library
Author	Attiya, Hagit Fich, Faith Ellen Kaplan, Yaniv
Abstract	An adaptive algorithm, whose step complexity adjusts to the number of active processes, is attractive for situations in which the number of participating processes is highly variable. This paper studies the number and type of multi-writer registers that are needed for adaptive algorithms. We prove that if a collect algorithm is f -adaptive to total contention, namely, its step complexity is f(k), where k is the number of processes that ever took a step, then it uses $Ω(f^{-1}(n)$ multi-writer registers, where n is the total number of processes in the system.Furthermore, we show that competition for the underlying registers is inherent for adaptive collect algorithms. We consider c-write registers, to which at most c processes can be concurrently about to write. Special attention is given to exclusive-write registers, the case c=1 where no competition is allowed, and concurrent-write registers, the case c=n where any amount of competition is allowed. A collect algorithm is f-adaptive to point contention, if its step complexity is f(k), where k is the maximum number of simultaneously active processes. Such an algorithm is shown to require $Ω(f^{-1}$ (nc)) concurrent-write registers, even if an unlimited number of c-write registers are available. A smaller lower bound is also obtained in this situation for collect algorithms that are f-adaptive to total contention.The lower bounds also hold for nondeterministic implementations of sensitive objects from historyless objects.Finally, we present lower bounds on the step complexity in solo executions (i.e., without any contention), when only c-write registers are used: For weak test&set objects, we present an Ω(log nlog c +log log n) lower bound. Our lower bound for collect and sensitive objects is Ω(n-1c).
Starting Page	60
Ending Page	69
Page Count	10
File Format	PDF
ISBN	1581138024
DOI	10.1145/1011767.1011777
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2004-07-25
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Weak test&set Adaptivity Collect Contention Solo termination Exclusive-write registers Sensitive objects
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