NDLI: Recurrence in Self-Stabilization

Content Provider	IEEE Xplore Digital Library
Author	Jubran, O. Theel, O.
Copyright Year	2015
Description	Author affiliation: Carl von Ossietzky Univ. of Oldenburg, Oldenburg, Germany (Jubran, O.; Theel, O.)
Abstract	Self-stabilization ensures that a system converges to a legitimate execution in finite time, where a legitimate execution comprises a sequence of configurations satisfying some safety condition. In this work, we investigate the notion of recurrence, which denotes how frequently a condition is satisfied in an execution of a system. We use this notion in self-stabilization to address the convergence of a system to a behavior that guarantees a minimum recurrence of some condition. We apply this notion to show how the design of distributed mutual exclusion algorithms can be altered to achieve a high service time under various convergence time and space complexities. As a particular contribution, we present a self-stabilizing mutual exclusion algorithm that has optimal service time together with optimal stabilization time complexity of (D/2 - 1) for synchronous executions and under any topology, where D is the diameter of the topology. In addition, we rectify an earlier proof stating that (D/2) is a lower bound, to conclude that (D/2 - 1) is optimal for synchronous executions.
Sponsorship	IEEE
Starting Page	58
Ending Page	67
File Size	322190
Page Count	10
File Format	PDF
ISBN	9781467393027
ISSN	10609857
DOI	10.1109/SRDS.2015.11
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-09-28
Publisher Place	Canada
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Convergence Topology Algorithm design and analysis Safety Transient analysis Time complexity Mutual Exclusion Distributed Algorithms Dependability Self-Stabilization Recurrence
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

Exploiting Synchronicity for Immediate Feedback in Self-Stabilizing PIF Algorithms

On the performance of Dijkstra’s third self-stabilizing algorithm for mutual exclusion and related algorithms

Two new quorum based algorithms for distributed mutual exclusion

On the Time Complexity of Dijkstra's Three-State Mutual Exclusion Algorithm

A fair starvation-free prioritized mutual exclusion algorithm for distributed systems

A distributed K-mutual exclusion algorithm

Self-stabilizing local mutual exclusion on networks in which process identifiers are not distinct

A Self-Stabilizing O(n)-Round k-Clustering Algorithm

Fair Comparison of Gossip Algorithms over Large-Scale Random Topologies

Recurrence in Self-Stabilization

Similar Documents

Exploiting Synchronicity for Immediate Feedback in Self-Stabilizing PIF Algorithms

On the performance of Dijkstra’s third self-stabilizing algorithm for mutual exclusion and related algorithms

Two new quorum based algorithms for distributed mutual exclusion

On the Time Complexity of Dijkstra's Three-State Mutual Exclusion Algorithm

A fair starvation-free prioritized mutual exclusion algorithm for distributed systems

A distributed K-mutual exclusion algorithm

Self-stabilizing local mutual exclusion on networks in which process identifiers are not distinct

A Self-Stabilizing O(n)-Round k-Clustering Algorithm

Fair Comparison of Gossip Algorithms over Large-Scale Random Topologies

Recurrence in Self-Stabilization