A mnlticast group is a collection of processesthat are the destinations of the same sequenceof messages.These messagesmay originate at one or more source sites and the destination processesmay run on one or more sites, not necessarily distinct.The nmlticast groups may overlap.A multieast protocol is responsible for the delivery of messagesto the appropriate processes.Someapplications require that the protocol provide someguaranteeson the order in which messagesare delivered.In addition, in many casesreliability of delivery is essential.In this paper we -&rracterize three ordering properties and discusstheir solutions.We concentrate on the multiple group ordering property, which guarantees that two messages destined to two processesare delivered in the samerelative order, even if they originate at different sourcesand are addreseedto different mnlticast groups.We present a new protocol called the propagation graph algorithm that solves the multiple group ordering problem by org-g sites logically into a forest.We present simulation results that illustrate the performance of our algorithm compared to other techniques for ordering multicasts.We address the issue of reliability by considering the various types of reliability a protocol can provide and exploring one of these types of reliability with the propagation graph algorithm.We also consider the reliability of other solutions.In many eases our new algorithm solves the problem with greater efficiency than previous solutions without sacrificing reliability.

Three ordering properties are characterized, namely, single-source, multiple-source, and multiple-group ordering, and their solutions are discussed. The multiple-group ordering property, which guarantees that two messages destined to two processes are delivered in the same relative order, even if they originate at different sources and are addressed to different multicast groups, is concentrated on. A protocol that solves the multiple-group ordering problem is presented. The issues of performance and reliability are addressed by providing comparisons with other techniques for ordering multicasts. In many cases this new algorithm solves the problem with greater efficiency than previous solutions without sacrificing reliability. It is pointed out that one disadvantage of the technique is that sometimes sites are required to handle messages which they do not need to deliver locally. These so-called extra nodes, however, do not occur frequently according to the experiments presented.>

Voting is used commonly to enforce mutual exclusion in distributed systems. Each node is assigned a number of votes, and only the group with a majority of votes is allowed to perform a restricted operation. This paper describes techniques for dynamically reassigning votes upon node or link failure, in an attempt to make the system more resilient to future failures. We focus on autonomous methods for achieving this, that is, methods that allow the nodes to make independent choices about changing their votes and picking new vote values, rather than group consensus techniques that require tight coordination among the remaining nodes. Protocols are given which allow nodes to install new vote values while still maintaining mutual exclusion requirements. The lemmas and theorems to validate the protocols are presented. A simple example shows how to apply the method to a database object-locking scheme; the protocols, however, are versatile andgeneral purpose, and can be used foranyapplication requiring mutual exclusion. In addition, policies are presented that allow nodes to autonomously select their new vote values. Simulation results are presented comparing the autonomous methods to static vote assignments and to group consensus strategies. These results demonstrate that under high failure rates, dynamic vote reassignment shows great improvement over a static assignment of votes in terms of availability. In addition, many autonomous methods for determining a new vote assignment yield almost as much availability as a group consensus method and at the same time are faster and more flexible.

Article Protocols for dynamic vote reassignment Share on Authors: Daniel Barbara Computer Science Department, Princeton University, Princeton, New Jersey Computer Science Department, Princeton University, Princeton, New JerseyView Profile , Hector Garcia-Molina Computer Science Department, Princeton University, Princeton, New Jersey Computer Science Department, Princeton University, Princeton, New JerseyView Profile , Annemarie Spauster Computer Science Department, Princeton University, Princeton, New Jersey Computer Science Department, Princeton University, Princeton, New JerseyView Profile Authors Info & Claims PODC '86: Proceedings of the fifth annual ACM symposium on Principles of distributed computingNovember 1986 Pages 195–205https://doi.org/10.1145/10590.10607Online:01 November 1986Publication History 25citation329DownloadsMetricsTotal Citations25Total Downloads329Last 12 Months8Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access