CS计算机代考程序代写 flex Java cache algorithm NWEN303 Concurrent Programming

NWEN303 Concurrent Programming
18: Ass3 Model answers and Clustering
Marco Servetto VUW

Ass3 model answers
Q1.1 Is ‘new Point(0,0)’ an expression referring to a deeply immutable object? Yes, all Point fields are final
Q1.2 Is ‘new Person(“bob”,new Point(0,0))’ an expression referring to a deeply immutable object?
No, Person fields can be mutated; however new Person(“bob”,new Point(0,0)) refers to an encapsulated object.
Q1.3 If a method has a parameter ‘Point x’, will x always refer to a deeply immutable object (or null)?
No, a class EvilPoint extends Point can be present somewhere else in the program.
Q1.4 If a method has a parameter ‘Person x’, will x always refer to a deeply immutable object (or null)?
No, Person is not immutable, since it has mutable fields.

Ass3 model answers
void msg1(String m){b.tell(new Point(0,0), self());}
Yes, new Point(0,0) will refer to a deeply immutable object (also to an encapsulated object)
void msg2(Integer m){b.tell(new Person(“Bob”,new Point(0,0)), self());}
Yes, new Person(..) will refer to an encapsulated object (not immutable)
The string “Bob” may not be encapsulated, Java may cache it and reuse it around, but that is ok since String is deeply immutable
void msg3(Double m){b.tell(this.point, self());}
No, the Point could be an instance of a mutable EvilPoint extends Point.
If it was leaked to another actor, then there will be two actors able to mutate it.
void msg4(Point m){b.tell(m, self());}
Yes, we know the point m is either encapsulated or deeply immutable, thus we can pass it as a message (since we do not store it!)
void msg5(Character m){b.tell(this.persons.get(0), self());}
No, the person in the array is not encapsulated, since it will continue to stay in the list. If it was leaked to another actor, then there will be two actors able to mutate it.

Ass3 model answers void msgHard(Person m){b.tell(m, self());}//1
Yes, we know the Person m is encapsulated, thus we can pass it as a message (since we do not store it!)
void msgHard(Person m){b.tell(new Person(“Bob”,m.location), self());}//2
Yes, we know the Person m is encapsulated, thus we can pass a part of it as a message (since we do not store it!).
Note that we do not know if m.location is deeply immutable.
void msgHard(Person m){b.tell(new Person(“Bob”,new Point(m.location.x,m.location.y)), self());}//3 Yes, we know that m.location.x/y are just primitive types, and we create a new Person with completely fresh data (except “Bob”), so the sent message is encapsulated.
void msgHard(Person m){this.persons.add(m); b.tell(m, self());}//4
No, the Person m was encapsulated when we received it, but now is saved in the list; Thus, it is no more encapsulated when is sent to the other actor.
Indeed, there will be two actors able to mutate it.
void msgHard(Person m){ this.persons.add(m); b.tell(m.deepClone(), self());}//5
No, The method deepClone is NON FINAL, thus EvilPerson extends Person could override it to leak the original person object. Thus case 5 may behave identical to case 4. If the method deepClone was final, then case 5 would have been correct.

Ass3 model answers void msgHard(Person m){ b.tell(this.persons, self());}//6
No, the list could now be reached by two actors. Indeed this.persons is not encapsulated.
void msgHard(Person m){b.tell(Collections.unmodifiableList(this.persons), self());}//7 No, unmodifiableList only wraps around the list, do not create a (deep) copy, thus the other actor could still
-observe concurrent mutation of the list
-concurrently mutate the Person objects inside of the list.
void msgHard(Person m){b.tell(new ArrayList<>(this.persons), self());} //8
No, this copy the list but do not create a deep copy of the persons,
thus the other actor could still concurrently mutate the Person objects inside of the list.
void msgHard(Person m){ b.tell(this.persons.subList(0, 3), self());} //9
No, the sublist is still baked on the original list, and the original Person objects, thus the other actor could still
-observe concurrent mutation of the list
-concurrently mutate the list
-concurrently mutate the Person objects inside of the list.

Ass3 model answers
Looking againt to msg3:
void msg3(Double m){b.tell(this.point, self());}
This would have been correct if the code for actor A was different: class A extends AbstractActor{
ActorRef b;
final Point point;
List persons;
A(ActorRef b, Point point, List persons){
this.b=b;
this.point=new Point(point.x,point.y);//now we know we store exactly a Point this.persons=persons;
}
Alternatively, if the class Point was declared final, again msg3 would be correct.
void msg5(Character m){b.tell(this.persons.get(0), self());}
No, the person in the array is not encapsulated, since it will continue to stay in the list.
If it was leaked to another actor, then there will be two actors able to mutate it.

Ass3 model answers
Looking againt to msg5:
void msg5(Character m){b.tell(this.persons.get(0), self());}
This is so much harder to make correct: void msg5(Character m){
Person p=this.persons.get(0); this.persons.remove(0); b.tell(p, self());
}
This would NOT WORK.
-The List persons could be EvilList extends List and do nothing for the remove. -The person in position 0 could be duplicated and present in other parts of the list. -Some other person in the list could be a PersonWithFriends extends Person
that have a list of Person friends that could be present in other parts of the list. -Two persons could share the same EvilPoint extends Point as position;
another way to inject an hidden mutable alias.

CLUSTERING

●
●
–
●
–
●
–
–
–
–
Hardware setup
I’m not an expert here. A minimal system may require to set up every machine with:
Hardware:Uninterruptible power supply (UPS), connected to the PC
Like a little battery so that the pc can survives a short black-out and other power irregularity. Even a very little battery, 5 minute worth, is sufficient.
Hardware: network controlled electric switch, connected to the UPS
A simple machine with an electric cable running through it. It can receive internet requests to allow or prevent current through such cable.
Bios: setting up the PC to restart after a power loss. The option should be under one of the following:
“Restore on AC/Power Loss”, “AC Power Recovery” or “After Power Loss”. sometime under “Advanced”, “ACPI” or “Power Management Setup”.
good UPS can tell the PC/BIOS to shut up gracefully as soon as it stays 30 second or more without power.
Operative System: restart OpenAkka or a similar program.

● ●
●
●
●
Cluster of nodes
We have a Cluster of Nodes, every Node is a machine and the Cluster is a connected set of nodes.
Every node can crash/fail.
The connection between nodes can be very unreliable.
We would like to know when that happens!
But, as when chatting…. can you distinguish a slow typist from an asleep one?
For a while, a slow pc/connection behave like a crashed machine.

Nodes and actors
Leader!
Main1 Alice Bob Tim .. .. .. ..
Main2 Hugo Rob Matt .. .. .. ..
Joe Sam Nael .. .. .. ..
● One actor for each node is the Main responsible for that node.
One Node is the leader node, its main actor is the leader actor.
Main3
●
All actors can talk with each other. Actors sit on specific machines: a node.
●

●
●
Cluster of nodes
We have a Cluster of Nodes, every Node is a machine and the Cluster is a connected set of nodes.
Every node have actors on it.
One actor will be the ‘node responsible’ (main):
either the root guardian or one chosen by the root guardian
One node of the cluster will be the Leader. Duplicated leaders are possible but more involved
Main actors perform node lifecicle activities
●
●

●
●
●
●
Nodes lifecicle
Main actors send messages to the main leader as following:
New node want to connect to cluster Node wish to gracefully disconnect.
Node is judged dead/crashed and is forcefully disconnected
Node send its ‘heart beat’

Cluster of nodes

●
●
●
A LOT
From 1 every second, to 100 every seconds
The main leader will record statistical analysis on the way the various heart beats arrived, the timing and sometime the ordering
Then… various algorithms apply.
Let see ‘The φ Accrual Failure Detector’
also used by akka clusters under the hood
●
–
How many heart beats?

●
The main idea is that the algorithm should only provide a ‘confidence number’ that the node is dead, but not a yes/no answer.
In this way the actors can take decisions based on the confidence level.
0-1 near certainty alive
3-6 probably dead if the network is good
8 probably dead even if the network is bad
12 probably dead even if the network is very bad
●
● ● ● ●
The φ Accrual Failure Detector

●
The purpose of those algorithms is to allow the leader to know the connectivity information of the cluster.
In most cases, the leader will broadcast such information to all the other nodes at a regular interval, much longer than the heart beats.
We will assume this broadcasting in the following.
●
●
The leader know the connectivity

●
●
●
The leader want to give tasks to actors in the other nodes to perform.
If a node is over 2.5, the leader will not give any new tasks to that node.
If a node is over 4, the leader start rescheduling the tasks given to such node to more responsive nodes, and it will chose whatever result comes first.
If a node drop over 8, it will contact the corresponding network controlled electric switch to reboot the node by cutting off the electric power long enough to restart that pc. When such machine will restart, it will try to connect again to the cluster.
●
Example behavior

●
–
●
–
There is a time after which correct nodes are not suspected by any correct node.
●
–
If node p is faulty, its suspicion level tends to infinity as time goes to infinity.
●
–
●
–
If node p is correct, then for any time t0, its suspicion levels will be 0 for some time t ≥ t0.
Properties
Property 1 (Strong completeness)
There is a time after which every node that crashes is permanently suspected by all correct nodes.
Property 2 (Eventual strong accuracy)
Property 3 (Accruement)
Property 4 (Unknown upper bound)
If node p is correct, then its suspicion level is bounded.
Property 5 (Reset)

●
–
●
Problem: we requires some process to act as a coordinator/leader.
●
–
●
In many systems, the coordinator is chosen by hand,
e.g. file servers. This leads to centralized solutions, containing a single point of failure.
Most algorithms assume that each node has a unique ID and the focus of the algorithm is locating the node with the highest ID and electing their main actor leader.
●
What if the leader Crashes? The nodes may want to elect a new Leader:
many leader election algorithms available
How to select this special process dynamically? especially after failure?

●
–
–
●
High-numbered nodes “bully” low-numbered nodes out of the election, until only one node remains.
When a crashed node reboots and try to join the cluster it holds an election. If it is now the highest- numbered live node, it will win, otherwise it will discover who is the current leader.
●
Bully Algorithm – Overview A main actor p calls an election when:
it notices that the leader is no longer acting (does not receive its broadcast about who is alive).
It still can reach (ping) ‘most’ other nodes in the network.

●
●
●
–
– –
Bully Algorithm – Overview
Principle:
The leader is always the node with the highest ID (weight).
Problem:
How do we find the non-failed node with the highest ID?
Assumptions:
All nodes know about each other
(using the last broadcast from the former leader)
Nodes numbered uniquely
They do not know each other’s state (up/crashed)

●
–
●
–
–
● ●
– –
Bully Algorithm – Overview
Suppose main actor p decided to start an election:
p Sends Election message to all higher numbered main actors from other nodes
If there is no response after a reasonable timeout, p takes over as leader, and send the message Coordinator to all the nodes.
Makes sense to physically restart all the nodes above him, they must be crashed/unresponsive.
All nodes can now record who is the new leader.
If there is any response, p have lost the election.
Suppose q receives Election message:
q replies Ok to sender, saying it will take over
q sends Election message to higher numbered processes

Node 4 notices 7 has failed,
starts election
Node 4 < 5 & 6, Node 5 starts Both 5 & 6 say an election “I will take over” (OK message) Bully Algorithm - Overview Bully Algorithm - Overview Node 5 < 6, Process 6 Node 6 announces it says “I will take over” is the winner (OK message) ● ● ● – ● Thus, Marco suggestion: do not attempt distributed critical section. Use actors as monitors. How to remotely execute personalized behavior on (actor-)monitored data? ● Distributed critical section Many algorithms are available Is costly and complex Mostly unneeded if we have actors as monitors most critical sections are needed to implement monitors or parts of monitors Code for a flexible Akka monitor class Data{/*...*/void update(){/*...*/}}//any encapsulated data class Monitor extends AbstractActor{ public static interface DataUpdate //lambda to update the data extends Consumer,Serializable{}
public static interface DataAsk //lambda to send info out
extends BiConsumer,Serializable{} private Data monitoredData;//initialized by constructor public Receive createReceive() {
return receiveBuilder() .match(DataUpdate.class,c->c.accept(monitoredData)) .match(DataAsk.class,c->c.accept(monitoredData,sender())) .build();}}
/*….*/
ActorRef monitor=/*…*/;
//just updating monitor.tell((Monitor.DataUpdate)d->d.update(),monitor); //possibly updating and also getting a value out of it CompletableFuture