NDLI: Message-optimal protocols for fault-tolerant broadcasts/multicasts in distributed systems with crash failures

Content Provider	IEEE Xplore Digital Library
Author	Hong-Yi Tzeng Kai-Yeung Siu
Copyright Year	1968
Abstract	An essential feature in any fault tolerant design of distributed systems is a mechanism by which a process can reliably broadcast information to other processes in the presence of failures. The paper studies the message complexity of fault tolerant broadcast protocols in weakly synchronous and totally asynchronous distributed systems with point to point communication links, where the system failures are caused by the processes but the communication links are completely reliable. We focus on the number of messages required of any fault tolerant protocol in failure free executions. Our motivation is that one should incur the cost of handling failures only when they actually occur. We present protocols that, in an n-process system subject to at most t crash failures where 1/spl les/t<(n-1), guarantee the delivery of a message from any process to other nonfaulty processes. In the absence of crash failures, our protocols require (n+t-1) messages in the weakly synchronous model and (t+1)(n--1-(t/2)) messages in the totally asynchronous model. Moreover, we show that in both cases our protocols are optimal with respect to message complexity. The new insights provided in our lower bound proofs also yield graph-theoretic characterizations of all message optimal reliable broadcast protocols in failure free executions. Both the upper and lower bound results on broadcast protocols can be generalized to multicast protocols, where a process only needs to deliver a message to a subset of processes in the system.<>
Sponsorship	IEEE Computer Society Technical Committee on Distributed Process IEEE Computer Society Technical Committee on VLSI IEEE Technical Committee on Computer Architecture IEEE Computer Society
Starting Page	346
Ending Page	352
Page Count	7
File Size	821430
File Format	PDF
ISSN	00189340
Volume Number	44
Issue Number	2
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1995-02-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Multicast protocols Fault tolerant systems Broadcasting Computer crashes Fault tolerance Distributed computing Costs
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics 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

Message-optimal protocols for reliable broadcasts in networks with crash failures

Consensus-based fault-tolerant total order multicast

Fault-tolerant Total Order Multicast to asynchronous groups

Fault tolerant algorithms for broadcasting on the star graph network

Fault-Tolerant Consensus in Unknown and Anonymous Networks

Atomic broadcast in asynchronous crash-recovery distributed systems

Crash-resilient time-free eventual leadership

The MAFT architecture for distributed fault tolerance

Randomized multivalued consensus

Message-optimal protocols for fault-tolerant broadcasts/multicasts in distributed systems with crash failures

Similar Documents

Message-optimal protocols for reliable broadcasts in networks with crash failures

Consensus-based fault-tolerant total order multicast

Fault-tolerant Total Order Multicast to asynchronous groups

Fault tolerant algorithms for broadcasting on the star graph network

Fault-Tolerant Consensus in Unknown and Anonymous Networks

Atomic broadcast in asynchronous crash-recovery distributed systems

Crash-resilient time-free eventual leadership

The MAFT architecture for distributed fault tolerance

Randomized multivalued consensus

Message-optimal protocols for fault-tolerant broadcasts/multicasts in distributed systems with crash failures