NDLI: Churn- and DoS-resistant Overlay Networks Based on Network Reconfiguration

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

Shuffles and Circuits: (On Lower Bounds for Modern Parallel Computation)

On Computational Thinking, Inferential Thinking and Data Science

Extending the Nested Parallel Model to the Nested Dataflow Model with Provably Efficient Schedulers

RUBIC: Online Parallelism Tuning for Co-located Transactional Memory Applications

Cache-Adaptive Analysis

General Profit Scheduling and the Power of Migration on Heterogeneous Machines

A Multicore Path to Connectomics-on-Demand

Robust and Probabilistic Failure-Aware Placement

Just Join for Parallel Ordered Sets

Universal Shape Formation for Programmable Matter

Lock-free Transactions without Rollbacks for Linked Data Structures

The Family Holiday Gathering Problem or Fair and Periodic Scheduling of Independent Sets

The Cost of Unknown Diameter in Dynamic Networks

Parallel Shortest Paths Using Radius Stepping

Parallel Algorithms for Summing Floating-Point Numbers

A Practical Solution to the Cactus Stack Problem

Extending TM Primitives using Low Level Semantics

Parallel Algorithms for Asymmetric Read-Write Costs

The Power of Migration in Online Machine Minimization

Brief Announcement: Flexible Resource Allocation for Clouds and All-Optical Networks

Parallel Equivalence Class Sorting: Algorithms, Lower Bounds, and Distribution-Based Analysis

Asymptotically Optimal Gathering on a Grid

Concurrent Search Data Structures Can Be Blocking and Practically Wait-Free

Election vs. Selection: How Much Advice is Needed to Find the Largest Node in a Graph?

Churn- and DoS-resistant Overlay Networks Based on Network Reconfiguration

Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford

Randomized Approximate Nearest Neighbor Search with Limited Adaptivity

Latency-Hiding Work Stealing: Scheduling Interacting Parallel Computations with Work Stealing

Investigating the Performance of Hardware Transactions on a Multi-Socket Machine

Brief Announcement: Preserving Happens-before in Persistent Memory

Fair Online Scheduling for Selfish Jobs on Heterogeneous Machines

Clairvoyant Dynamic Bin Packing for Job Scheduling with Minimum Server Usage Time

Parallel Approaches to the String Matching Problem on the GPU

Better Bounds for Coalescing-Branching Random Walks

Fast and Robust Memory Reclamation for Concurrent Data Structures

Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures

Fast Distributed Algorithms for Connectivity and MST in Large Graphs

Parallelism in Randomized Incremental Algorithms

Encoding Short Ranges in TCAM Without Expansion: Efficient Algorithm and Applications

Provably Good and Practically Efficient Parallel Race Detection for Fork-Join Programs

Brief Announcement: Transactional Data Structure Libraries

Brief Announcement: Approximating the I/O Complexity of One-Shot Red-Blue Pebbling

Scheduling Parallelizable Jobs Online to Minimize the Maximum Flow Time

Brief Announcement: Improved Approximation Algorithms for Scheduling Co-Flows

Brief Announcement: MIC++: Accelerating Maximal Information Coefficient Calculation with GPUs and FPGAs

Brief Announcement: Benchmarking Concurrent Priority Queues:

Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond

Brief Announcement: A Tight Distributed Algorithm for All Pairs Shortest Paths and Applications

Brief Announcement: Dynamic Determinacy Race Detection for Task Parallelism with Futures

Brief Announcement: A QPTAS for Non-preemptive Speed-scaling

Online Packet Scheduling for CIOQ and Buffered Crossbar Switches

Brief Announcement: Fast Concurrent Cuckoo Kick-Out Eviction Schemes for High-Density Tables

Brief Announcement: Relaxed Byzantine Vector Consensus

Brief Announcement: Energy Optimization of Memory Intensive Parallel Workloads

Churn- and DoS-resistant Overlay Networks Based on Network Reconfiguration

Content Provider	ACM Digital Library
Author	Drees, Maximilian Gmyr, Robert Scheideler, Christian
Abstract	We present three robust overlay networks: First, we present a network that organizes the nodes into an expander and is resistant to even massive adversarial churn. Second, we develop a network based on the hypercube that maintains connectivity under adversarial DoS-attacks. For the DoS-attacks we use the notion of a Ω(log log n)-late adversary which only has access to topological information that is at least Ω(log log n) rounds old. Finally, we develop a network that combines both churn- and DoS-resistance. The networks gain their robustness through constant network reconfiguration, i.e., the topology of the networks changes constantly. Our reconfiguration algorithms are based on node sampling primitives for expanders and hypercubes that allow each node to sample a logarithmic number of nodes uniformly at random in O(log log n) communication rounds. These primitives are specific to overlay networks and their optimal runtime represents an exponential improvement over known techniques. Our results have a wide range of applications, for example in the area of scalable and robust peer-to-peer systems.
Starting Page	417
Ending Page	427
Page Count	11
File Format	PDF
ISBN	9781450342100
DOI	10.1145/2935764.2935783
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-11
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Dos-attack Expander Overlay network Random walks Hypercube Churn
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