NDLI: Optimal Local Buffer Management for Information Gathering with Adversarial Traffic

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

Beyond P vs. NP: Quadratic-Time Hardness for Big Data Problems

Randomized Composable Coresets for Matching and Vertex Cover

Asymptotically Optimal Approximation Algorithms for Coflow Scheduling

Bounding Laconic Proof Systems by Solving CSPs in Parallel

Some Sequential Algorithms are Almost Always Parallel

Distributed Partial Clustering

Is Our Model for Contention Resolution Wrong?: Confronting the Cost of Collisions

Concurrent Data Structures for Near-Memory Computing

Near Optimal Parallel Algorithms for Dynamic DFS in Undirected Graphs

Online Tree Caching

Almost Optimal Streaming Algorithms for Coverage Problems

Online Flexible Job Scheduling for Minimum Span

Matrix Multiplication, a Little Faster

Distributed Detection of Cycles

Optimal Reissue Policies for Reducing Tail Latency

Lower Bounds in the Asymmetric External Memory Model

Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing

Provably Efficient Scheduling of Cache-oblivious Wavefront Algorithms

Bicriteria Distributed Submodular Maximization in a Few Rounds

Minimizing Total Weighted Flow Time with Calibrations

A Communication-Avoiding Parallel Algorithm for the Symmetric Eigenvalue Problem

Distributed Graph Clustering by Load Balancing

Impact of Knowledge on Election Time in Anonymous Networks

Hand-Over-Hand Transactions with Precise Memory Reclamation

Improved Cover Time Bounds for the Coalescing-Branching Random Walk on Graphs

Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers: Extended Abstract

On Energy Conservation in Data Centers

Tight Bounds for Clairvoyant Dynamic Bin Packing

Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource

Fast Scheduling in Distributed Transactional Memory

Swarm-based Incast Congestion Control in Datacenters Serving Web Applications

Optimal Local Buffer Management for Information Gathering with Adversarial Traffic

The Mobile Server Problem

Brief Announcement: Meeting the Challenges of Parallelizing Sequential Programs

Brief Announcement: Scheduling Parallelizable Jobs Online to Maximize Throughput

Brief Announcement: Graph Matching in Massive Datasets

Brief Announcement: Approximation Algorithms for Unsplittable Resource Allocation Problems with Diseconomies of Scale

Brief Announcement: Parallel Dynamic Tree Contraction via Self-Adjusting Computation

Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack

Brief Announcement: Hazard Eras - Non-Blocking Memory Reclamation

Brief Announcement: A New Improved Bound for Coflow Scheduling

Brief Announcement: Using Multi-Level Parallelism and 2-3 Cuckoo Filters for Set Intersection Queries and Sparse Boolean Matrix Multiplication

Brief Announcement: Towards Fault-Tolerant Bin Packing for Online Cloud Resource Allocation

Brief Announcement: STAR (Space-Time Adaptive and Reductive) Algorithms for Dynamic Programming Recurrences with more than O(1) Dependency

Brief Announcement: Complete Visibility for Oblivious Robots in Linear Time

Brief Announcement: Extending Transactional Memory with Atomic Deferral

Brief Announcement: Hardware Transactional Storage Class Memory

Optimal Local Buffer Management for Information Gathering with Adversarial Traffic

Content Provider	ACM Digital Library
Author	Narayanan, Lata Dobrev, Stefan Lafond, Manuel Opatrny, Jaroslav
Abstract	We consider a problem of routing on directed paths and trees to a single destination, with rate-limited, adversarial traffic. In particular, we focus on local buffer management algorithms that ensure no packet loss, while minimizing the size of the required buffers. While a centralized algorithm for the problem that uses constant-sized buffers has been recently shown [21], there is no known local algorithm that achieves a sub-linear buffer size. In this paper we show tight bounds for the maximum buffer size needed by l-local algorithms for information gathering on directed paths and trees, where an algorithm is called l-local if the decision made by each node v depends only on the sizes of the buffers at most l hops away from v. We show three main results: A lower bound of Ω(c log n/l) for all l-local algorithms on both directed and undirected paths, where c is an upper bound on the link capacity and injection rate. A surprisingly simple 1-local algorithm for directed paths that uses buffers of size O(log n), when c=1. A natural 2-local extension of this algorithm to directed trees, for c=1, with the same asymptotic bound. Our Ω(log n) lower bound is significantly lower than the Ω(n) lower bound for greedy algorithms, and perhaps surprisingly, there is a matching upper bound. The algorithm that achieves it can be summarized in two lines: If the size of your buffer is odd, forward a message if your successor's buffer size is equal or lower. If your buffer size is even, forward a message only if your successor's buffer size is strictly lower. For trees, a simple arbitration between siblings is added.
Starting Page	265
Ending Page	274
Page Count	10
File Format	PDF
ISBN	9781450345934
DOI	10.1145/3087556.3087577
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-07-24
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Local algorithms Trees Information gathering Buffer size Directed paths Routing Adversarial traffic Buffers
Content Type	Text
Resource Type	Article

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

Dynamic Routing on Networks with Fixed-Size Buffers (2003)

Rate vs. buffer size: greedy information gathering on the line

Dynamic Routing on Networks with Fixed-Size Buffers (Extended Abstact) (2003)

Rate vs. Buffer size -- greedy information gathering on the line (2007).

Information gathering in adversarial systems: lines and cycles

Optimal dynamic routing in communication networks with continuous traffic

Rate vs. buffer size--greedy information gathering on the line

Buffer Size for Routing Limited-Rate Adversarial Traffic

Dynamic routing on networks with fixed-size buffers (Extended Abstract) (2003)

Optimal Local Buffer Management for Information Gathering with Adversarial Traffic

Similar Documents

Dynamic Routing on Networks with Fixed-Size Buffers (2003)

Rate vs. buffer size: greedy information gathering on the line

Dynamic Routing on Networks with Fixed-Size Buffers (Extended Abstact) (2003)

Rate vs. Buffer size -- greedy information gathering on the line (2007).

Information gathering in adversarial systems: lines and cycles

Optimal dynamic routing in communication networks with continuous traffic

Rate vs. buffer size--greedy information gathering on the line

Buffer Size for Routing Limited-Rate Adversarial Traffic

Dynamic routing on networks with fixed-size buffers (Extended Abstract) (2003)

Optimal Local Buffer Management for Information Gathering with Adversarial Traffic