DistOS-2011W Failure Detection in Distributed Systems - Revision history

Hadi sajjadpour: /* References */

2011-03-09T02:20:50Z

References

← Older revision		Revision as of 02:20, 9 March 2011
Line 141:		Line 141:

	[3] P. Felber, X. Defago, R. Guerraoui, and P. Oser. Failure detectors as first class objects. In Proceedings of the International Symposium on Distributed Objects and Applications, 1999. The version I used here is from 2002.		[3] P. Felber, X. Defago, R. Guerraoui, and P. Oser. Failure detectors as first class objects. In Proceedings of the International Symposium on Distributed Objects and Applications, 1999. The version I used here is from 2002.

	[4] N. Hayashibara, A. Cherif, T. Katayama, Failure Detectors for Large-Scale Distributed Systems, In 21st IEEE Symposium of Reliable Distributed Systems (SRDS’ 02). 2002		[4] N. Hayashibara, A. Cherif, T. Katayama, Failure Detectors for Large-Scale Distributed Systems, In 21st IEEE Symposium of Reliable Distributed Systems (SRDS’ 02). 2002

Hadi sajjadpour: /* Introduction */

2011-03-09T02:19:31Z

Introduction

← Older revision		Revision as of 02:19, 9 March 2011
Line 7:		Line 7:
	= Introduction =		= Introduction =

			In my literature review, I first talk a little about the history of failure detectors in distributed systems, then move on to define the most used/known protocols used to monitor in between local processes, then move on to introducing their drawbacks, and then mention some work done in solving those drawbacks.
	In my literature review, I first talk a little about the history of failure detectors in distributed systems, then move on to define the most used/known protocols used to monitor in between local processes, then move on to introducing their drawbacks, and then mention some work done in solving those drawbacks.

	~~Most of what I learnt in this task were from papers [3] and [4] as they have beautifully categorized everything~~.

	= History =		= History =

Hadi sajjadpour at 02:18, 9 March 2011

2011-03-09T02:18:05Z

← Older revision		Revision as of 02:18, 9 March 2011
Line 1:		Line 1:
			Seyyed Sajjadpour

	= Abstract =		= Abstract =

Hadi sajjadpour: /* The Pull Model */

2011-03-09T00:23:20Z

The Pull Model

← Older revision		Revision as of 00:23, 9 March 2011
Line 44:		Line 44:
	Assume that we have the same parameters as above. In this model, instead of the process q (the one that has to prove its alive) sending messages to p every few seconds, it sends ‘are you alive?’ messages to q every t seconds, and waits for q to respond ‘yes I am alive’ [3,4]. The figure below is used in both [3] and [4] with a minute difference in each.		Assume that we have the same parameters as above. In this model, instead of the process q (the one that has to prove its alive) sending messages to p every few seconds, it sends ‘are you alive?’ messages to q every t seconds, and waits for q to respond ‘yes I am alive’ [3,4]. The figure below is used in both [3] and [4] with a minute difference in each.

	[[File:Fig2.png\|400px\|thumb\|center\|The Pull Model]]		[[File:Fig2.png\|400px\|thumb\|center\|The Pull Model [3,4]]]

	In the above figure, p repeatedly checks if q is alive, and if q is alive it will respond with the 'I am alive' heartbeat message. Once q crashes, p does not receive any more responses from q and starts suspecting the failure of q after a timeout T time.		In the above figure, p repeatedly checks if q is alive, and if q is alive it will respond with the 'I am alive' heartbeat message. Once q crashes, p does not receive any more responses from q and starts suspecting the failure of q after a timeout T time.

Hadi sajjadpour: /* The Push Model */

2011-03-09T00:23:04Z

The Push Model

← Older revision		Revision as of 00:23, 9 March 2011
Line 35:		Line 35:
	Assuming that we have two processes, p and q. With p being the process that is the monitor. Process q will be sending heartbeat messages every t seconds, hence process p will be expecting a “I am alive message” from q every t seconds. Heartbeat messages are messages that are sent on a timely bases to inform/get informed about a process. If after a timeout period T, p does not receive any messages from q, then it starts suspecting q [3,4]. The figure below is used in both [3] and [4] with a minute difference in each.		Assuming that we have two processes, p and q. With p being the process that is the monitor. Process q will be sending heartbeat messages every t seconds, hence process p will be expecting a “I am alive message” from q every t seconds. Heartbeat messages are messages that are sent on a timely bases to inform/get informed about a process. If after a timeout period T, p does not receive any messages from q, then it starts suspecting q [3,4]. The figure below is used in both [3] and [4] with a minute difference in each.

	[[File:fig1.png\|400px\|thumb\|center\|Push Model]]		[[File:fig1.png\|400px\|thumb\|center\|Push Model [3,4]]]

	As you can see in the figure, process q is sending heartbeat messages periodically. At one point it crashes and it stops sending messages. Process p, waiting for heartbeat messages, at this point does not receive any more messages, and after a timeout period of T, suspects that q has failed.		As you can see in the figure, process q is sending heartbeat messages periodically. At one point it crashes and it stops sending messages. Process p, waiting for heartbeat messages, at this point does not receive any more messages, and after a timeout period of T, suspects that q has failed.

Hadi sajjadpour: /* Gossip-Style Failure Detection */

2011-03-09T00:17:29Z

Gossip-Style Failure Detection

← Older revision		Revision as of 00:17, 9 March 2011
Line 108:		Line 108:

	In [3], they draw a diagram in which they mix both the hierarchical model and the [2]’s gossip model. The figure is as follows:		In [3], they draw a diagram in which they mix both the hierarchical model and the [2]’s gossip model. The figure is as follows:

			[[File:Fig5_hadi.png\|800px\|thumb\|center\|Gossip + Hierarchical model]]

	There have been other work done in gossip-style failure detection [15].		There have been other work done in gossip-style failure detection [15].

Hadi sajjadpour: /* The Hierarchical Model */

2011-03-09T00:13:48Z

The Hierarchical Model

← Older revision		Revision as of 00:13, 9 March 2011
Line 73:		Line 73:
	3) Monitorable objects in the hierarchical model. I will illustrate this by the figure below from [3], note I redrew the figure myself to avoid any copyright issues.		3) Monitorable objects in the hierarchical model. I will illustrate this by the figure below from [3], note I redrew the figure myself to avoid any copyright issues.

			[[File:fig4_hadi.png\|700px\|thumb\|center\|The hierarchical model [3]]]

	In the figure, FD1, FD2, FD3 and FD3’ are all monitors/failure detectors. As you can notice the monitors are not all in the same LAN, however, each monitor only monitors monitorable objects in its own LAN. While monitoring the monitorables, they also notify the clients of the status of the objects they need to know about. This model greatly reduces the amount of messages exchanged in between process. Instead of the clients monitoring every object that is monitorable, monitors do so and notify the clients when necessary or when they ask for it. On top of that, monitors also ask other monitors about their monitorable objects, hence they do not need to communicate with every other monitorable object. Again this reduces the heartbeat messages exchanged. In the given example, even if FD3 or FD3’ fail, the clients will not notice it as messages can be routed through another path.		In the figure, FD1, FD2, FD3 and FD3’ are all monitors/failure detectors. As you can notice the monitors are not all in the same LAN, however, each monitor only monitors monitorable objects in its own LAN. While monitoring the monitorables, they also notify the clients of the status of the objects they need to know about. This model greatly reduces the amount of messages exchanged in between process. Instead of the clients monitoring every object that is monitorable, monitors do so and notify the clients when necessary or when they ask for it. On top of that, monitors also ask other monitors about their monitorable objects, hence they do not need to communicate with every other monitorable object. Again this reduces the heartbeat messages exchanged. In the given example, even if FD3 or FD3’ fail, the clients will not notice it as messages can be routed through another path.

Hadi sajjadpour: /* The Hierarchical Model */

2011-03-09T00:11:42Z

The Hierarchical Model

← Older revision		Revision as of 00:11, 9 March 2011
Line 66:		Line 66:
	== The Hierarchical Model ==		== The Hierarchical Model ==

	This model is an appropriate model for a LAN. In [3], they introduce three different elements exists (by summary) 1) Clients ~~2) Monitors 3) Monitorable objects in the hierarchical model. I will illustrate this by the figure below from [3], note I redrew the figure myself to avoid any copyright issues.~~		This model is an appropriate model for a LAN. In [3], they introduce three different elements exists (by summary)
			1) Clients

			2) Monitors

			3) Monitorable objects in the hierarchical model. I will illustrate this by the figure below from [3], note I redrew the figure myself to avoid any copyright issues.

	In the figure, FD1, FD2, FD3 and FD3’ are all monitors/failure detectors. As you can notice the monitors are not all in the same LAN, however, each monitor only monitors monitorable objects in its own LAN. While monitoring the monitorables, they also notify the clients of the status of the objects they need to know about. This model greatly reduces the amount of messages exchanged in between process. Instead of the clients monitoring every object that is monitorable, monitors do so and notify the clients when necessary or when they ask for it. On top of that, monitors also ask other monitors about their monitorable objects, hence they do not need to communicate with every other monitorable object. Again this reduces the heartbeat messages exchanged. In the given example, even if FD3 or FD3’ fail, the clients will not notice it as messages can be routed through another path.

			In the figure, FD1, FD2, FD3 and FD3’ are all monitors/failure detectors. As you can notice the monitors are not all in the same LAN, however, each monitor only monitors monitorable objects in its own LAN. While monitoring the monitorables, they also notify the clients of the status of the objects they need to know about. This model greatly reduces the amount of messages exchanged in between process. Instead of the clients monitoring every object that is monitorable, monitors do so and notify the clients when necessary or when they ask for it. On top of that, monitors also ask other monitors about their monitorable objects, hence they do not need to communicate with every other monitorable object. Again this reduces the heartbeat messages exchanged. In the given example, even if FD3 or FD3’ fail, the clients will not notice it as messages can be routed through another path.

	== Gossip-Style Failure Detection ==		== Gossip-Style Failure Detection ==

Hadi sajjadpour: /* More Complex Methods */

2011-03-09T00:11:24Z

More Complex Methods

← Older revision		Revision as of 00:11, 9 March 2011
Line 59:		Line 59:

	1) The Hierarchical Method		1) The Hierarchical Method

	2) Gossip-style Failure Detection		2) Gossip-style Failure Detection

	3) The Accrual Failure Detector		3) The Accrual Failure Detector

Hadi sajjadpour: /* The Dual Scheme */

2011-03-09T00:09:24Z

The Dual Scheme

← Older revision		Revision as of 00:09, 9 March 2011
Line 50:		Line 50:
	== The Dual Scheme ==		== The Dual Scheme ==

	The pull model is somehow inefficient as there are potentially too many messages sent between the processes. The pull model is a bit more efficient in this manner. Hence, in [4] they propose a model that is a mix of the two. During the first message sending phase, any q like process that is being monitored by p, is assumed to use the push model, and hence send “ I am alive” or “liveness” messages to p. After some time, p assumes that any q like process that did not send a liveness message is using the pull model. The figure below is only in [4].		The pull model is somehow inefficient as there are potentially too many messages sent between the processes. The pull model is a bit more efficient in this manner. Hence, in [3] they propose a model that is a mix of the two. During the first message sending phase, any q like process that is being monitored by p, is assumed to use the push model, and hence send “ I am alive” or “liveness” messages to p. After some time, p assumes that any q like process that did not send a liveness message is using the pull model. The figure below is only in [3].

			[[File:Fig3_hadi.png\|500px\|thumb\|center\|The Dual Model[3]]]

	= More Complex Methods =		= More Complex Methods =