{"id":129,"date":"2018-08-19T12:52:01","date_gmt":"2018-08-19T12:52:01","guid":{"rendered":"http:\/\/nitk.acm.org\/blog\/?p=129"},"modified":"2018-08-19T12:52:01","modified_gmt":"2018-08-19T12:52:01","slug":"group-membership-protocols","status":"publish","type":"post","link":"https:\/\/nitk.acm.org\/blog\/2018\/08\/19\/group-membership-protocols\/","title":{"rendered":"Group Membership Protocols"},"content":{"rendered":"

What are Group Membership Protocols?<\/strong><\/p>\n

In data centers, failures are the norm rather than the exception. Google fellow Jeff Dean offers an overview of Google\u2019s data center operations:<\/p>\n

\u201cIn each cluster\u2019s first year, it\u2019s typical that 1,000 individual machine failures will occur; thousands of hard drive failures will occur; one power distribution unit will fail, bringing down 500 to 1,000 machines for about 6 hours; 20 racks will fail, each time causing 40 to 80 machines to vanish from the network; 5 racks will \u201cgo wonky,\u201d with half their network packets missing in action; and the cluster will have to be rewired once, affecting 5 percent of the machines at any given moment over a 2-day span, Dean said. And there\u2019s about a 50 percent chance that the cluster will overheat, taking down most of the servers in less than 5 minutes and taking 1 to 2 days to recover.\u201d<\/em><\/p>\n

We need a mechanism to detect failures and disseminate the failure information through the network. This is where Group Membership Protocols come into picture. We give every process a membership list. A membership list contains the list of all processes along with its last heartbeat. (Heartbeat refers to the last time the process P communicated with the current process.)<\/p>\n

Now that every process has a membership list, we need to detect failures. Once a failure is detected, this process needs to be removed from all membership lists. How do we achieve this?<\/p>\n

Heartbeat Protocol<\/strong><\/p>\n

A process P sends a heartbeat(message) to process Q telling that it is alive. If P does not receive the heartbeat, it assumes that process Q is dead.<\/p>\n

The topology could be varied. All processes might send heartbeats to a centralized node or they could send it to all other processes.<\/p>\n

\"\"<\/p>\n

There are some very obvious disadvantages here. Centralized Heartbeat-ing is dependent on one central process. If that fails, everything fails. All to All Heartbeat-ing has an increased overhead of sending heartbeats to all the processes.<\/p>\n

So how do we optimise?<\/p>\n

Gossip- Style Membership<\/strong><\/p>\n

Every process randomly selects n processes and sends them a heartbeat. Each of these processes will update their membership lists and send out a heartbeat to n processes again randomly selected. If the heartbeat does not increase even after T_fail seconds, the process is considered fail. It waits for another T_cleanup seconds before it deletes the member from the membership list.<\/p>\n

\"\"
Gossip Membership Protocol (by Indranil Gupta)<\/figcaption><\/figure>\n

A single heartbeat takes O(log N) time to propagate and N heartbeats take O(N log(N)) time.<\/p>\n

Can we optimize further?<\/p>\n

SWIM Failure Detector Protocol<\/strong><\/p>\n

SWIM (Scalable Weakly-consistent Infection-style) uses membership lists along with a protocol period T. A process Pi randomly picks a process Pj in its membership list and pings it. If it does not receive an ACK within the timeout period, it selects k other targets and uses them to send a message to Pj. The ACK is passed on from these k targets to Pi. If Pi doesn\u2019t receive an ACK within T, it declares Pj as failed.<\/p>\n

\"\"
SWIM Protocol (by Indranil Gupta)<\/figcaption><\/figure>\n
\n
\n
<\/div>\n<\/div>\n<\/figure>\n
Data centers use more complex failure prediction and detection models which use these protocols as the building blocks.<\/div>\n
<\/div>\n
<\/div>\n
– Sunitha Selvan<\/em><\/div>\n","protected":false},"excerpt":{"rendered":"

What are Group Membership Protocols? In data centers, failures are the norm rather than the exception. Google fellow Jeff Dean offers an overview of Google\u2019s data center operations: \u201cIn each cluster\u2019s first year, it\u2019s typical that 1,000 individual machine failures will occur; thousands of hard drive failures will occur; one power distribution unit will fail,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[10],"tags":[],"class_list":["post-129","post","type-post","status-publish","format-standard","hentry","category-tech"],"_links":{"self":[{"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/posts\/129","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/comments?post=129"}],"version-history":[{"count":3,"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/posts\/129\/revisions"}],"predecessor-version":[{"id":135,"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/posts\/129\/revisions\/135"}],"wp:attachment":[{"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/media?parent=129"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/categories?post=129"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nitk.acm.org\/blog\/wp-json\/wp\/v2\/tags?post=129"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}