Distributed Systems 07. Group Communication Paul Krzyzanowski Rutgers University Fall 2014 1 September 30, 2014 © 2014 Paul KrzyzanowskiModes of communication • unicast – 1↔1 – Point-to-point • anycast – 1→nearest 1 of several identical nodes – Introduced with IPv6; used with BGP • “netcast” – 1 →many but 1 at a time • multicast – 1→many – group communication • broadcast – 1→all 2 September 30, 2014 © 2014 Paul KrzyzanowskiGroups Groups allow us to deal with a collection of processes as one abstraction Send message to one entity – Deliver to entire group Groups are dynamic – Created and destroyed – Processes can join or leave • May belong to 0 or more groups Primitives – join_group, leave_group, send_to_group, query_membership 3 September 30, 2014 © 2014 Paul KrzyzanowskiDesign Issues • Closed vs. Open – Closed: only group members can sent messages • Peer vs. Hierarchical – Peer: each member communicates with group – Hierarchical: go through dedicated coordinator(s) – Diffusion: send to other servers & clients • Managing membership & group creation/deletion – Distributed vs. centralized • Leaving & joining must be synchronous • Fault tolerance – Reliable message delivery? What about missing members? 4 September 30, 2014 © 2014 Paul KrzyzanowskiFailure considerations • Crash failure – Process stops communicating • Omission failure (typically due to network) – Send omission: A process fails to send messages – Receive omission: A process fails to receive messages • Byzantine failure – A message is faulty • Partition failure – The network may get segmented into two or more unreachable groups September 30, 2014 © 2014 Paul Krzyzanowski 5Implementing Group Communication Mechanisms September 30, 2014 © 2014 Paul Krzyzanowski 6Hardware multicast Hardware support for multicast – Group members listen on network address listen addr = m1 listen addr = m1 listen addr = m1 send addr=m1 7 September 30, 2014 © 2014 Paul KrzyzanowskiHardware broadcast Hardware support for broadcast – Software filters multicast address • May be auxiliary address broadcast(id=m) accept id=m accept id=m accept id=m discard id=m discard id=m 8 September 30, 2014 © 2014 Paul KrzyzanowskiSoftware: “netcast” Multiple unicasts – Sender knows group members listen local addr = a2 listen local addr = a3 listen local addr = a5 send(a2) send(a3) 9 September 30, 2014 © 2014 Paul KrzyzanowskiSoftware: hierarchical Multiple unicasts via group coordinator – coordinator knows group members listen local addr = a2 listen local addr = a3 listen local addr = a5 coordinator send(a2) send(a3) send(c) 10 September 30, 2014 © 2014 Paul KrzyzanowskiReliability of multicasts September 30, 2014 © 2014 Paul Krzyzanowski 11Atomic multicast Atomicity Message sent to a group arrives at all group members • If it fails to arrive at any member, no member will process it Problems Unreliable network • Each message should be acknowledged • Acknowledgements can be lost Message sender might die 12 September 30, 2014 © 2014 Paul KrzyzanowskiAchieving atomicity (2-phase commit variation) Retry through network failures & system downtime Sender and receivers maintain persistent log 1. Send message to all group members • Each receiver acknowledges message • Saves message and acknowledgement in log • Does not pass message to application 2. Sender waits for all acknowledgements • Retransmits message to non-responding members – Again and again… until responses from all are received – Now the sender knows all group members have received the message 3. Sender sends “deliver” message to all members • Each recipient delivers message to application • Sends reply to server 13 September 30, 2014 © 2014 Paul KrzyzanowskiAchieving atomicity • All members will eventually get the message – Phase 1: • Make sure that everyone gets the message – Phase 2: • Once everyone has confirmed receipt, let the application see it • If a machine dies, it checks its persistent log to find its state in the protocol and recover the message • Lots of other protocols • All of them consume resources and time September 30, 2014 © 2014 Paul Krzyzanowski 14Reliable multicast • All non-faulty group members will receive the message – Assume sender & recipients will remain alive – Network may have glitches • Retransmit undelivered messages • Acknowledgements – Send message to each group member – Wait for acknowledgement from each group member – Retransmit to non-responding members – Subject to feedback implosion • Negative acknowledgements – Use a sequence # on each message – Receiver requests retransmission of a missed message – More efficient but requires sender to buffer messages indefinitely September 30, 2014 © 2014 Paul Krzyzanowski 15Unreliable multicast (best effort) • Basic multicast • Hope it gets there 16 September 30, 2014 © 2014 Paul KrzyzanowskiMessage ordering September 30, 2014 © 2014 Paul Krzyzanowski 17Good Ordering Process 0 message a order received a, b a, b message b 18 September 30, 2014 © 2014 Paul KrzyzanowskiBad Ordering Process 0 message a order received a, b b, a message b 19 September 30, 2014 © 2014 Paul KrzyzanowskiGood Ordering Process 0 Process 1 message a message b order received a, b a, b 20 September 30, 2014 © 2014 Paul KrzyzanowskiBad Ordering Process 0 Process 1 message a message b order received a, b b, a 21 September 30, 2014 © 2014 Paul KrzyzanowskiSending versus Delivering • Multicast receiver algorithm decides when to deliver a message to the process. • A received message may be: – Delivered immediately (put on a delivery queue that the process reads) – Placed on a hold-back queue (because we need to wait for an earlier message) – Rejected/discarded (duplicate or earlier message that we no longer want) 22 September 30, 2014 © 2014 Paul KrzyzanowskiSending, delivering, holding back sender receiver Multicast sending algorithm Multicast receiving algorithm hold-back queue delivery queue discard ? message transmission deliver 23 September 30, 2014 © 2014 Paul