NDLI: Dining philosophers with crash locality 1

Content Provider	IEEE Xplore Digital Library
Author	Pike, S.M. Sivilotti, P.A.G.
Copyright Year	2004
Description	Author affiliation: Ohio State Univ., Columbus, OH, USA (Pike, S.M.; Sivilotti, P.A.G.)
Abstract	Ideally, distributed algorithms isolate the side-effects of faults within local neighborhoods of impact. Failure locality quantifies this concept as the maximum radius of impact caused by a given fault. We present new locality results for the dining philosophers problem subject to crash failures. The optimal crash locality for dining is 0 in synchronous networks, but degrades to 2 in asynchronous networks. Using the eventually-perfect failure detector /spl diams/P , we construct the first known dining algorithms with crash locality 1 under partial synchrony. These algorithms close the failure-locality complexity gap and improve the crash tolerance of resource allocation algorithms in practical networks. We prove the optimality of our results with two fundamental theorems. First, no dining solution using /spl diams/P achieves locality 0. Second, /spl diams/P is the weakest failure detector in the Chandra-Toueg hierarchy to realize locality 1.
Sponsorship	IEEE Comput. Soc. Information Processing Soc. of Japan (IPSJ)
Starting Page	22
Ending Page	29
File Size	579481
Page Count	8
File Format	PDF
ISBN	0769520863
ISSN	10636927
DOI	10.1109/ICDCS.2004.1281564
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2004-03-26
Publisher Place	Japan
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computer crashes Detectors Distributed algorithms Resource management Degradation Fault tolerant systems Topology Timing
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

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

Crash-resilient time-free eventual leadership

Dining philosophers that tolerate malicious crashes

Fault-Tolerant Aggregation for Dynamic Networks

On node state reconstruction for fault tolerant distributed algorithms

Fault-Tolerant Consensus in Unknown and Anonymous Networks

Decentralized Local Failure Detection in Dynamic Distributed Systems

Efficient fault-tolerant algorithms for distributed resource allocation

Total order multicast to multiple groups

Atomic broadcast in asynchronous crash-recovery distributed systems

Dining philosophers with crash locality 1

Similar Documents

Crash-resilient time-free eventual leadership

Dining philosophers that tolerate malicious crashes

Fault-Tolerant Aggregation for Dynamic Networks

On node state reconstruction for fault tolerant distributed algorithms

Fault-Tolerant Consensus in Unknown and Anonymous Networks

Decentralized Local Failure Detection in Dynamic Distributed Systems

Efficient fault-tolerant algorithms for distributed resource allocation

Total order multicast to multiple groups

Atomic broadcast in asynchronous crash-recovery distributed systems

Dining philosophers with crash locality 1