NDLI: A Self-Stabilizing Minimal k-Grouping Algorithm

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

Multi-valued Asynchronous Reliable Broadcast with a Strict Honest Majority

Local Checkability in Dynamic Networks

Time-communication trade-offs for minimum spanning tree construction

Accountability in Dynamic Networks

Scalable MapReduce-based Fuzzy Min-Max Neural Network for Pattern Classification

Topology-aware resource management for HPC applications

An Architecture for SDN Based Sensor Networks

PPRP: Predicted Position Based Routing Protocol Using Kalman Filter for Vehicular Ad-hoc Network

Total Order Reliable Convergecast in WBAN

An NDNoT based Efficient Object Searching Scheme for Smart Home using RFIDs

Minimizing Network Traffic Features for Android Mobile Malware Detection

Implementation and Performance Evaluation of Name-based Forwarding Schemes in V-NDN

A Resilient Self-Organizing Offshore Communication Network for Fishermen

Practical Multi-threaded Graph Coloring Algorithms for Shared Memory Architecture

Reinforcing Immutability of Permissioned Blockchains with Keyless Signatures' Infrastructure

Probabilistic Byzantine Tolerance Scheduling in Hybrid Cloud Environments

Distributed Computation of Mixing Time

Lock-free Linearizable 1-Dimensional Range Queries

Secure Multiparty Construction of a Distributed Social Network

Feasibility of Fog Computing Deployment based on Docker Containerization over RaspberryPi

Optimized Offloading Using Local Clusters

FastRank: Practical Lightweight Tolerance to Rational Behaviour in Edge Assisted Streaming

A Novel Priority Based Exigent Data Diffusion Approach for Urban VANets

Best Effort Broadcast under Cascading Failures in Interdependent Networks

Efficient Algorithms for Power Maximization in the Vector Model for Wireless Energy Transfer

Contemporary IT Security for Military Online Collaboration Platforms

A Planning Based Approach for Context Aware Services Composition in Pervasive Systems: Short Paper

Performance Assessment of an Extremely Challenged Mobile Infrastructure Network over the Oceans

Balancing Maximal Independent Sets using Hadoop

A Self-Stabilizing Minimal k-Grouping Algorithm

Fault-tolerant Gathering of Semi-synchronous Robots

Efficient Algorithms for Predicate Detection using Hybrid Logical Clocks

Energy-Aware Scheduling of Periodic Conditional Task Graphs on MPSoCs

Improved Write Access Control and Stronger Freshness Guarantee to Outsourced Data

Dynamic Pricing for Maximizing Cloud Revenue: A Column Generation Approach

An Energy-efficient and Buffer-aware Routing Protocol for Opportunistic Smart Traffic Management

SER Performance of OFDM-Based AF and DF Cooperative Networks over Asymmetric Fading Channels

Are We Birds of the Same Feather?

Coalitional Game Theory based Cooperative Spectrum Sensing in CRNs

Exploring the Impact of Connectivity on Dissemination of Post Disaster Situational Data over DTN

On Diameter Based Community Structure Identification in Networks

Fault-Tolerant Gathering of Mobile Robots with Weak Multiplicity Detection

Exact, Fast and Scalable Parallel DBSCAN for Commodity Platforms

Disaster-aware WDM network design for data centres

Towards Smart City: Sensing Air Quality in City based on Opportunistic Crowd-sensing

Energy Aware Cluster Head Load Balancing Scheme for Heterogeneous Wireless Ad Hoc Network

A Self-Stabilizing Minimal k-Grouping Algorithm

Content Provider	ACM Digital Library
Author	Larmore, Laurence L. Masuzawa, Toshimitsu Datta, Ajoy K. Sudo, Yuichi
Abstract	We consider the minimal k-grouping problem: given a graph G = (V, E) and a constant k, partition G into subgraphs of diameter no greater than k, such that the union of any two subgraphs has diameter greater than k. We give a silent self-stabilizing asynchronous distributed algorithm for this problem in the composite atomicity model of computation, assuming the network has unique process identifiers. Our algorithm works under the weakly-fair daemon. The time complexity (i.e. the number of rounds to reach a legitimate configuration) of our algorithm is O (nD/k) where n is the number of processes in the network and D is the diameter of the network. The space complexity of each process is O((n + nfalse) log n) where nfalse is the number of false identifiers, i.e., identifiers that do not match the identifier of any process, but which are stored in the local memory of at least one process at the initial configuration. Our algorithm guarantees that the number of groups is at most 2n/k + 1 after convergence. We also give a novel composition technique to concatenate a silent algorithm repeatedly, which we call loop composition.
Starting Page	1
Ending Page	10
Page Count	10
File Format	PDF
ISBN	9781450348393
DOI	10.1145/3007748.3007772
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-01-05
Publisher Place	New York
Access Restriction	Subscribed
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