NDLI: On the message and time complexity of protocols for reliable broadcasts/multicasts in networks with omission failures

Content Provider	IEEE Xplore Digital Library
Author	Hong-Yi Tzeng Kai-Yeung Siu
Copyright Year	1983
Abstract	This paper presents a fundamental study on the message and time complexity of reliable broadcast/multicast protocols in point-to-point networks subject to omission failures. We assume a weakly synchronous model in which there is a known upper bound on the delay in delivering a message from one process to another. A faulty process may omit sending or receiving messages; this characterizes a common faulty behavior in networking applications. We focus our study on the number of messages and the maximum amount of time required of any fault-tolerant protocol in failure-free executions. We present protocols that, in an n-process network subject to at most t faulty processes, guarantee the delivery of a message from any process to all other nonfaulty processes. In particular, when no failure occurs in the network, our protocols require (n+t-1) messages and at most (n-1+upper bound [log/sub 2/(t+1)])/spl middot//spl delta/ units of time, where /spl delta/ is the maximum time required to deliver a message from a process to another. Moreover, we show that our protocols are optimal with respect to message and time complexity. The new insights provided by the lower bound proofs yield a graph-theoretic characterization of all message and time optimal reliable broadcast/multicast protocols in failure-free executions. We further discuss the implications of our results on the support of multicast services in high-speed switching networks such as ATM.<>
Starting Page	1296
Ending Page	1308
Page Count	13
File Size	1480804
File Format	PDF
ISSN	07338716
Volume Number	13
Issue Number	7
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1995-09-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 Broadcasting Intelligent networks Asynchronous transfer mode Fault tolerance Local area networks Delay Upper bound Ethernet networks Token networks
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Electrical and Electronic Engineering

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

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

Efficient ordered broadcasting in reliable CSMA/CD networks

ATM LAN emulation

Implementation of efficient and reliable multicast servers

Streets of Byzantium: Network Architectures for Fast Reliable Broadcasts

Cells in frames: ATM over legacy networks

Bounds for performance measures of token rings

Fault tolerance for token-based synchronization protocols

On the message and time complexity of protocols for reliable broadcasts/multicasts in networks with omission failures

Similar Documents

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

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

Efficient ordered broadcasting in reliable CSMA/CD networks

ATM LAN emulation

Implementation of efficient and reliable multicast servers

Streets of Byzantium: Network Architectures for Fast Reliable Broadcasts

Cells in frames: ATM over legacy networks

Bounds for performance measures of token rings

Fault tolerance for token-based synchronization protocols

On the message and time complexity of protocols for reliable broadcasts/multicasts in networks with omission failures