7 - synchronizers Flashcards
What is the purpose of synchronizers?
run non fault-tolerant synchronous distributed algorithms in asynchronous systems
What is the basic idea of synchronizers?
let the processes proceed in simulated round. ensure that a message sent at round r is received by its destination before it starts round r+. check whether a node has received all messages of a round then let a synchronizer generate a “clock pulse” (= new round)
Explain the properties of alpha-synchronisers
- communication on all point-to-point links
- communication-inefficient
- time-efficient
Explain the properties of beta-synchronisers
- elect leader, and create spanning tree from that node.
- communication along branches of this tree.
- communication-efficient
- time-inefficient
Explain the properties of gamma-synchronisers
- Combine alpha- and beta-synchronizers.
- synchronize between cluster nodes via alpha (intercluster)
- synchronize inside each clusters using beta-synchronizers (intracluster)
Explain how a new clock pulse is generated for alpha synchronizers.
First, each node that sends out an message will wait for an ACK from its neighbours. When all ACKs have been received, a node sees itself as safe, so it sends a SAFE. A node knows to generate a new pulse / iteration when all its neighbours are safe as well.
Explain how a new clock pulse is generated for beta synchronizers.
First, the root sends out a pulse. Each node will concider if it is SAFE when it has received all its expected messages and all its decended nodes are SAFE. It then sends a SAFE upwards (to the root) The root generates a new pulse when the root declares itself SAFE (under the same conditions)
skip
What is the difference in pulse generation for alpha and beta synchronization?
In beta, the PULSE can only be generated and send by the root, and the other nodes immediatly accept that the network is now safe. In alpha, a SAFE is required from all neighbours in order accept safety.
How many links are there between two neighbouring gamma clusters?
only 1, these are called preferred links. It can be that a cluster is connected to multiple different clusters tho
Explain how a new pulse is generated in gamma-synchronization. (with signals!)
The beta-trees will first send a PULSE and wait for all SAFE responses from its descendends.
Then the beta cluster controller will send a CLUSTER_SAFE downwards, this signal is also send across prefered links. Then when node has received a CLUSTER_SAFE from all its links, it will send a READY. When the controller has received a READY from all nodes in its cluster.
So nodes with a prefered link need 2 CLUSTER_SAFEs in order to produce a READY.
In gamma synchronization, do READYs cross preferred links?
No, only CLUSTER_SAFEs
