NDLI: A lower bound on dynamic k-stabilization in asynchronous systems

Content Provider	IEEE Xplore Digital Library
Author	Genolini, C. Tixeuil, S.
Copyright Year	2002
Description	Author affiliation: Univ. de Paris X Nanterre, France (Genolini, C.)
Abstract	It is desirable that the smaller the number of faults hitting a network, the faster a network protocol recovers. We study the scenario where up to k (for a given k) faults hit processors of a synchronous distributed system by corrupting their state undetectably. In this context, we show that the well known step complexity model is not appropriate to study time complexity of time-adaptive protocols (i.e. protocols that recover from memory corruption in a time that depends only on the number of faults and not on the network size). In more detail, we prove that for nontrivial dynamic problems (such as token passing), there exists a lower bound of /spl Omega/(D) (where D is the network diameter) steps on the stabilization time even when as few as 1 corruption can hit the system. This implies that there exists no time adaptive protocol for those problems in the asynchronous step model, even if we assume that the number of faults is bounded by 1 and that the scheduling of the processors is almost synchronous (between two actions of an enabled processor any other processor may execute at most one action).
Sponsorship	IEEE Comput. Soc. Tech. Committee on Distributed Process. IEEE Comput. Soc. Tech. Committee on Fault-Tolerant Comput. IFIP WG 10.4 on Dependable Comput. & Fault Tolerance IEICE Dependable Comput. Tech. Group Graduate School of Inf. Sci. & Technol., Osaka Univ
Starting Page	212
Ending Page	221
File Size	513746
Page Count	10
File Format	PDF
ISBN	0769516599
ISSN	10609857
DOI	10.1109/RELDIS.2002.1180190
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2002-10-13
Publisher Place	Japan
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Protocols Modems Iris Robustness Resilience Taxonomy Processor scheduling Upper bound Hamming distance Fault detection
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computer Networks and Communications Software 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

Service time optimal self-stabilizing token circulation protocol on anonymous undirectional rings

Fault-local stabilization : the shortest path tree

Decentralized Local Failure Detection in Dynamic Distributed Systems

Supporting dynamic space-sharing on clusters of non-dedicated workstations

Self-stabilization with global rooted synchronizers

Ongoing fault diagnosis

A user-customizable energy-adaptive combined static/dynamic scheduler for mobile applications

A multiprocessor scheduling algorithm for low overhead fault-tolerance

Enhancing real-time schedules to tolerate transient faults

A lower bound on dynamic k-stabilization in asynchronous systems

Similar Documents

Service time optimal self-stabilizing token circulation protocol on anonymous undirectional rings

Fault-local stabilization : the shortest path tree

Decentralized Local Failure Detection in Dynamic Distributed Systems

Supporting dynamic space-sharing on clusters of non-dedicated workstations

Self-stabilization with global rooted synchronizers

Ongoing fault diagnosis

A user-customizable energy-adaptive combined static/dynamic scheduler for mobile applications

A multiprocessor scheduling algorithm for low overhead fault-tolerance

Enhancing real-time schedules to tolerate transient faults

A lower bound on dynamic k-stabilization in asynchronous systems