Design Pattern: Master-Slave

Intention

• Need to implement complex service

• Need separation of concern

• Need organization of work not structural decomposition as in Whole-Part

Introduction

• Supports fault tolerance, parallel computation and computational accuracy

• Master distributes work to identical slave components

• Computes a final result from the results these slaves return

Example

• Traveling-salesman problem

• Well-known graph theory

• Find an optimal round trip between a given set of locations, such as the shortest trip that visit each location exactly once

• 6.0828 * 10**62 different trips that connect the state capitals of the United States

• Thus, find the best out of (n-1)! with n location

Context

• Partitioning work into semantically-identical sub-tasks

Problem

• Use "Divide and Conquer"

• Partitioned into several equal sub-tasks that are processed independently

• Clients should not be aware that the calculation is based on the divide and conquer principle

• Clients or processing of sub-tasks should not depend on algorithms for partitioning work and assembling the final result

• In order to increase computational accuracy, different implementation can be used

• Sub-tasks might need coordination

Solution

• Introduce a coordination instance between clients of the service and the processing of individual sub-tasks

• A Master component divides work into equal sub-tasks, distributes these sub-tasks to Slave components

• Provide all slaves with a common interface. The clients will only communicate with the Master

• Traveling-salesman - mutliple compared with fixed number of trips randomly and compared at the Master level

Applicability

• Fault tolerance - Service is delegated to serveral replicated implementations, so failure can be detected and handled

• Paralled computing - pipelining on different processing unit (unit does not just mean processor)

• Computational accurancy - Inaccurate results can be detected and handled

Structure

• Again: Divide and Conquer

• Offers an interface that allows clients to access this service

• Master: partitioning work, maintaining Slave reference, starting and controlling their processing, computing the final result

• Slave: provides sub-service defined by the Master

• Master to Slave, One to Many relation

General Scenario

Client call Master

Master internally split work, callSlaves

Slaves are called and sub-result returns

Master internally combine results

Result return to Client

Implementation

Five simple steps

• Divide work - specify how the computation can be splited using math algo, domain info, etc

• Combine sub-task - specify how the final result of the whole service can be computed with the sub-results from Slave

• Define the cooperation between Master and Slave - Define interface (between master and slave) while dividing work. Interface functions implemented by the Slave

Can be implemented as passing parameters sharing or using separated data sturcture

Can be implemented as folking off Slave with the Master environment variables

Depends on initial problem

• Implement the Slave components in previous step

Classic example in database processing with data warehouse type of query

Build logical query plans - then pick the best one (using separate data structure)

After picking the best one, distributed out the work to Slave again with different interface for processing the picked plan

• Implement the Master according to the specification in the first three steps

Split work into fix number of sub-tasks

Define as many sub-tasks as necessary

Need to handle when some Slave failed

Need to pipeline if necessary (e.g. IO will block, where computation usually goes faster, etc)

Variants

• Slaves as Processes: To handle slaves located in separate processes

• Master as controller, Slaves as distributed objects (Web server vs Applets)

• Slaves as Java Thread (What is the disadvantage ?)

• Master-Slaves with inter-Slave coordination (Pipeline)

Consequences

Advantages

• Exchangeablility and externsibility: Can use an Slave abstract class, we can add., replace Slave without impacting the clients

• Separation of concerns: Master do coordination, Slave do specific tasks

• Efficiency: support parallel computation

Disadvantages

• Feasibility: Not always feasible. Not everything can partition, control over when, what to execute, predict storage space and other resources

• Machine dependency: One parallel processing program usually cannot be ported use to another machine. What about Java Thread ... what happen if Java Thread can take advantages of parallelism for you under the cover...