NDLI: New bounds for the controller problem

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

New bounds for the controller problem

Content Provider	Springer Nature Link
Author	Emek, Yuval Korman, Amos
Copyright Year	2010
Abstract	The (M, W)-controller, originally studied by Afek, Awerbuch, Plotkin, and Saks, is a basic distributed tool that provides an abstraction for managing the consumption of a global resource in a distributed dynamic network. The input to the controller arrives online in the form of requests presented at arbitrary nodes. A request presented at node u corresponds to the “desire” of some entity to consume one unit of the global resource at u and the controller should handle this request within finite time either by granting it with a permit or by denying it. Initially, M permits (corresponding to M units of the global resource) are stored at a designated root node. Throughout the execution permits can be transported from place to place along the network’s links so that they can be granted to requests presented at various nodes; when a permit is granted to some request, it is eliminated from the network. The fundamental rule of an (M, W)-controller is that a request should not be denied unless it is certain that at least M − W permits are eventually granted. The most efficient (M, W)-controller known to date has message complexity $${O (N\log^{2} N \log \frac{M}{W + 1})}$$ , where N is the number of nodes that ever existed in the network (the dynamic network may undergo node insertions and deletions). In this paper we establish two new lower bounds on the message complexity of the controller problem. We first prove a simple lower bound stating that any (M, W)-controller must send $${\Omega (N \log \frac{M}{W + 1})}$$ messages. Second, for the important case when W is proportional to M (this is the common case in most applications), we use a surprising reduction from the (centralized) monotonic labeling problem to show that any (M, W)-controller must send Ω(N log N) messages. In fact, under a long lasting conjecture regarding the complexity of the monotonic labeling problem, this lower bound is improved to a tight Ω(N log2 N). The proof of this lower bound requires that N = O(M) which turns out to be somewhat inevitable due to a new construction of an (M, M/2)-controller with message complexity O(N log2 M).
Starting Page	177
Ending Page	186
Page Count	10
File Format	PDF
ISSN	01782770
Journal	Distributed Computing
Volume Number	24
Issue Number	3
e-ISSN	14320452
Language	English
Publisher	Springer-Verlag
Publisher Date	2010-09-30
Publisher Place	Berlin/Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	(M, W)-controller Monotonic labeling Computer Systems Organization and Communication Networks Computer Communication Networks Computer Hardware Software Engineering/Programming and Operating Systems Theory of Computation
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computer Networks and Communications Computational Theory and Mathematics Hardware and Architecture

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

The mailbox problem

Tight bounds for parallel randomized load balancing

Upper and lower bounds for deterministic broadcast in powerline communication networks

Proof labeling schemes

General compact labeling schemes for dynamic trees

Gradient clock synchronization

Randomized leader election

Efficient distributed computation of distance sketches in networks

Tight bounds for k-set agreement with limited-scope failure detectors

New bounds for the controller problem

Similar Documents

The mailbox problem

Tight bounds for parallel randomized load balancing

Upper and lower bounds for deterministic broadcast in powerline communication networks

Proof labeling schemes

General compact labeling schemes for dynamic trees

Gradient clock synchronization

Randomized leader election

Efficient distributed computation of distance sketches in networks

Tight bounds for k-set agreement with limited-scope failure detectors

New bounds for the controller problem