Epidemic algorithms:
These are a class of algorithms that strive to disseminate
existing information and overcome reliability and scalability problems.
Dissemination protocols are hampered by scalability problems and there is
usually a tradeoff between reliability and scalability. They are applicable to use cases where the
scale is to the tune of millions of nodes and without any real-time information
dissemination is not required.
The term epidemics pertains to the spread of disease or
infection in terms of populations of individuals and the rate of change. It
starts from an individual and spreads by transmission. The goal of these
protocols is to spread the update as fast and completely as possible.
There are two styles of epidemic protocols. The first is
Anti-entropy and the second is Rumor-mongering.
In Anti-entropy algorithms, each peer p periodically
contacts a random partner q selected from the current population. Then, p and q
engage in an information exchange protocol, where updates known to p but not to
q are transferred from p to q (push), or vice-versa (pull), or in
both-direction (push-pull).
In Rumor-mongering algorithms, peers are initially ignorant.
When an update is learned by a peer, it becomes a hot rumour. When a peer holds
a hot rumour, it periodically chooses a random peer from the current population
and sends (pushes) the rumor to it. Eventually, a node will lose interest in
spreading the rumor. There are different modes for these operations. The loss
of interest can be explained by a counter analogy where one loses interest
after k contacts or by a coin or random analogy where one loses interest with a
probability of 1/k. Also, one can lose interest as feedback versus blind mode.
One loses interest in Feedback mode only if the recipient knows the rumor and
one loses interest in blind mode regardless of the recipient.
The reason that epidemic protocols scale is that the
participants’ load is independent of size and information spreads in log(system
size) time. With such fast scaling, they find usage in aggregations, membership
management and topology management.
The design space for such algorithms can be articulated in
the form of three axis for a 3D space. These axes are each for Peer Selection,
View Propagation, and View Selection.
Peer Selection increases with Rand method for uniform random selection
and Tail method for highest age. The View Propagation increases from algorithms
involving push mode to those involving push-pull mode. The View Selection
increases from Blind mode to Healer mode to Swapper mode.
Gossip-based Peer Sampling Protocol will shuffle requests
and responses at chosen peers. The state update progresses from these peers.
Newscast as a peer sampling example will involve a uniform
random peer selection, a push-pull view propagation and a Healer view
selection. A Newscast peer will pick a random peer from its view, send each
other view along with its own fresh link. It will keep c freshest links by
removing own info and duplicates. The information will be tracked based on
sender id and virtual time.
Cyclon as a peer sampling example will involve a highest age
Tail strategy for peer selection, a push-pull mode for view propagation, and a
Swapper mode for view selection. A Cyclon peer will pick the oldest peer from
its view and remove it from the view. It will exchange some of the peers in
neighbours via (swap policy) and the active peer sends its fresh address.
#codingexercise
You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i]
= [numberOfBoxesi, numberOfUnitsPerBoxi]:
- numberOfBoxesi is the number of boxes of
type i.
- numberOfUnitsPerBoxi is the
number of units in each box of the type i.
You are also given an integer truckSize, which is the maximum number
of boxes that can be put on the truck. You can choose
any boxes to put on the truck as long as the number of boxes does not
exceed truckSize.
Return the maximum total
number of units that can be put on the truck.
Example 1:
Input: boxTypes =
[[1,3],[2,2],[3,1]], truckSize = 4
Output: 8
Explanation:
There are:
- 1
box of the first type that contains 3 units.
- 2
boxes of the second type that contain 2 units each.
- 3
boxes of the third type that contain 1 unit each.
You
can take all the boxes of the first and second types, and one box of the third
type.
The
total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.
Example 2:
Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]],
truckSize = 10
Output: 91
Constraints:
- 1
<= boxTypes.length <= 1000
- 1
<= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
- 1
<= truckSize <= 106
class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
var boxMap = new TreeMap<Integer, List<Integer>>();
for (int i = 0; i < boxTypes.length; i++) {
var type = boxTypes[i][0];
var countOfUnits = boxTypes[i][1];
if (boxMap.containsKey(countOfUnits)){
var list = boxMap.get(countOfUnits);
list.add(type);
boxMap.put(countOfUnits, list);
} else {
var list = new ArrayList<Integer>();
list.add(type);
boxMap.put(countOfUnits, list);
}
}
int total = 0;
int totalUnits = 0;
for (var entry : boxMap.descendingMap().entrySet()){
var countOfUnits = entry.getKey();
var types = entry.getValue();
for (var type : types){
if (total + 1 <= truckSize) {
for (int i = 0; i < type && total < truckSize;
i++) {
total += 1;
totalUnits += 1 * countOfUnits;
}
} else {
return totalUnits;
}
}
}
return totalUnits;
}
}
Input
boxTypes =
[[1,3],[2,2],[3,1]]
truckSize =
4
Output
8
Expected
8
Input
boxTypes =
[[5,10],[2,5],[4,7],[3,9]]
truckSize =
10
Output
91
Expected
91
No comments:
Post a Comment