Database Reference
In-Depth Information
all the logic and controls. All other processes are denoted as slave processes. As
such, the interaction between processes is asymmetrical, whereby bidirectional con-
nections are established between the master and all the slaves, and no interconnec-
tion is permitted between any two slaves (see Figure 1.12a). This requires that the
master keeps track of every slave's network location within what is referred to as a
metadata structure. In addition, this entails that each slave is always capable of iden-
tifying and locating the master.
The master in master/slave organizations can distribute the work among the slaves
using one of two protocols, push-based or pull-based . In the push-based protocol,
the master assigns work to the slaves without the slaves asking for that. Clearly, this
might allow the master to apply fairness over the slaves via distributing the work
equally among them. In contrast, this could also overwhelm/congest slaves that are
currently experiencing some slowness/failures and are unable to keep up with work.
Consequently, load imbalance might occur, which usually leads to performance deg-
radation. Nevertheless, smart strategies can be implemented by the master. In par-
ticular, the master can assign work to a slave if and only if the slave is observed to be
ready for that. For this to happen, the master has to continuously monitor the slaves
and apply some certain logic (usually complex) to accurately determine ready slaves.
The master has also to decide upon the amount of work to assign to a ready slave so
as fairness is maintained and performance is not degraded. In clouds, the probability
of faulty and slow processes increases due to heterogeneity, performance unpredict-
ability, and scalability (see Section 1.5 for details on that). This might make the push-
based protocol somehow inefficient on the cloud.
Unlike the push-based protocol, in the pull-based protocol, the master assigns
work to the slaves only if they ask for that. This highly reduces complexity and
potentially avoids load imbalance, since the decision of whether a certain slave is
ready to receive work or not is delegated to the slave itself. Nonetheless, the master
still needs to monitor the slaves, usually to track the progresses of tasks at slaves
and/or apply fault-tolerance mechanisms (e.g., to effectively address faulty and slow
tasks, commonly present in large-scale clouds).
To this end, we note that the master/slave organization suffers from a single point
of failure (SPOF). Specifically, if the master fails, the entire distributed program
comes to a grinding halt. Furthermore, having a central process (i.e., the master) for
controlling and managing everything might not scale well beyond a few hundred
slaves, unless efficient strategies are applied to reduce the contention on the master
(e.g., caching metadata at the slaves so as to avoid accessing the master upon each
request). In contrary, using a master/slave organization simplifies decision making
(e.g., allow a write transaction on a certain shared data). In particular, the master is
always the sole entity that controls everything and can make any decision single-
handedly without bothering anyone else. This averts the employment of voting
mechanisms [23,71,72], typically needed when only a group of entities (not a single
entity) have to make decisions. The basic idea of voting mechanisms is to require a
task to request and acquire the permission for a certain action from at least half of
the tasks plus one (a majority). Voting mechanisms usually complicate implementa-
tions of distributed programs. Lastly, as specific examples, Hadoop MapReduce and
Pregel adopt master/slave organizations and apply the pull-based and the push-based
Search WWH ::




Custom Search