pydistsim.demo_algorithms.santoro2007.mega_merger.algorithm.MegaMergerAlgorithm

class MegaMergerAlgorithm(*args, **kwargs)

Bases: NodeAlgorithm

Mega-Merger

This algorithm is a distributed algorithm that elects a single node in a network. The way it works is by creating cities (a grouping of nodes) and merging them together, while maintaining a tree structure with a root (the downtown node) that makes the decisions.

Ultimately, when the cities are merged, the downtown node is elected as the root of the tree.

The algorithm is based on the descriptions in the book Design and Analysis of Distributed Algorithms by Nicola Santoro.

Parameters

percentage_of_initiatorsfloat

The percentage of initiators in the network.

INF_WEIGHTT

Value representing infinity.

WEIGHT_LISTlist[T] | Callable[[int], T]

Mapping of weights for the links.

CITY_LISTlist[T] | Callable[[int], T]

Mapping of cities in the network.

Methods

__init__
add_child
add_internal_link
add_observers
alarm
apply_restrictions	Apply all applicable restrictions.
block_inbox	Block the inbox of a node, so that only messages that satisfy the filter can be processed.
block_msg
check_algorithm_initialization	Check if the algorithm's current state matches the expected initial state.
check_algorithm_termination	Check if the algorithm's current state matches the expected termination state.
check_restrictions	Check if the restrictions are satisfied.
clear_observers
close	Close the inbox of the node for a specific neighbor.
default
default_INITIATOR
disable_alarm	Disable an alarm.
disable_all_node_alarms	Disable all alarms set for the node.
fire_next_are_you_outside	Assumes there are external links
get_external_links
get_internal_links
initializer	Method used to initialize the algorithm.
is_done_asking_outside
is_friendly_merge
is_halted	Check if the distributed algorithm has come to an end or deadlock, i.e. there are no messages to pass and no alarms set.
is_initialized
is_termination
log_ignore
log_received
notify_observers
on_are_you_outside	Handles the 'are you outside' message received by a node.
on_awakening
on_external	Handles the reception of an external message by a node.
on_internal	Handles the internal message received by a node.
on_let_us_merge	Handles the LET_US_MERGE message received by a node.
on_merge_me	Handles the MERGE_ME message received by a node.
on_min_link_weight	Handles the event when a minimum link weight message is received by a node.
on_notification	Handles the notification message received by a node.
on_termination
open	Open the inbox of the node for a specific neighbor.
partial_termination	Handles the partial termination of a node in the Mega Merger algorithm.
receiving
receiving_ASKING_OUTSIDE
receiving_COMPUTING_MIN_WEIGHTS
receiving_NOT_ELECTED
receiving_SLEEPING
receiving_WAITING_PARENT
reset	Reset the algorithm to its initial state.
reset_meta
send	Send content to destination, with header.
send_INF_WEIGHT
send_let_us_merge	Sends a 'LET_US_MERGE' message from the given node to its link with the minimum weight.
send_msg	Send a message to nodes listed in message's destination field.
set_alarm	Set an alarm for the node.
set_city
set_parent
spontaneously
step
unblock_by_header
unblock_inbox	Unblock the inbox of a node, so that all messages can be processed.
update_alarm_time	Update the time of an alarm by adding a time difference.
update_link_with_min_weight
when_city_change	Handles the event when a node's city changes.
when_friendly_merge
when_termination

Attributes

INI
S_init	Tuple of statuses that nodes should have at the beginning of the algorithm.
S_term	Tuple of statuses that nodes should have at the end of the algorithm.
algorithm_restrictions	Tuple of restrictions that must be satisfied for the algorithm to run.
default_params
network
required_params
nwm	Node wrapper manager.

S_init = (MMStatus.INITIATOR, MMStatus.SLEEPING)

Tuple of statuses that nodes should have at the beginning of the algorithm.

S_term = (MMStatus.ELECTED, MMStatus.NOT_ELECTED)

Tuple of statuses that nodes should have at the end of the algorithm.

Status

alias of MMStatus

algorithm_restrictions = (<class 'pydistsim.restrictions.communication.BidirectionalLinks'>, <class 'pydistsim.restrictions.reliability.TotalReliability'>, <class 'pydistsim.restrictions.topological.Connectivity'>)

Tuple of restrictions that must be satisfied for the algorithm to run.

fire_next_are_you_outside(node: MMNode)

Assumes there are external links

initializer()

Method used to initialize the algorithm. Is always called first. NodeAlgorithm subclasses may want to reimplement it.

Base implementation sends an INI message to the node with the lowest id and applies all restrictions.

on_are_you_outside(node: MMNode, message: Message)

Handles the ‘are you outside’ message received by a node.

This method processes the message to determine if the node is part of the same city as the sender or if it is outside. Depending on the city levels and the source of the message, it will either handle the message internally, send an internal or external response, or block the message.

on_external(node: MMNode, message: Message)

Handles the reception of an external message by a node.

This method is called when a node receives a message confirming the link leads to an external node. It updates the node’s state and processes the message according to the Mega Merger algorithm.

Behavior:

• Sets the node’s external_received flag to True.

• If the message source is not the expected link, logs a debug message and ignores the message.

• Updates the node’s status to COMPUTING_MIN_WEIGHTS (prev. was ASKING_OUTSIDE).

• Updates the link with the minimum weight.

• If the node is done asking outside:

  • If the node is the downtown, sends a “let us merge” message.

  • If the node is not the root, sends the minimum link weight to the parent node and updates the

  node’s status.

• If the minimum weight is infinite, triggers partial termination.

on_internal(node: MMNode, message: Message)

Handles the internal message received by a node.

This method processes an internal message received by a node and updates the node’s state accordingly. It performs the following actions: - Sets as internal the link between the node and the message source. - Checks if the message source is the expected link asking outside.

• If not, logs a debug message and ignores the message.

• Updates the node’s status to COMPUTING_MIN_WEIGHTS if the message source is the expected.

• If the node is done asking outside:

  • If the node is the root, triggers a new merge or the global termination.

  • If the node is not the root, sends the minimum link weight to the parent node.

on_let_us_merge(node: MMNode, message: Message)

Handles the LET_US_MERGE message received by a node.

This method processes the LET_US_MERGE message and determines the appropriate action based on the relationship between the sender and the receiver nodes, as well as their respective cities and levels.

Actions: - If the sender’s city is the same as the receiver’s city, sends the LET_US_MERGE message down the tree. - If the merge is considered friendly, it triggers a friendly merge. - If the receiver’s city level is higher than the sender’s, it triggers a forced merge. - If the receiver’s city level is the same as the sender’s, it blocks the message. - Otherwise, it ignores the message.

on_merge_me(node: MMNode, message: Message)

Handles the MERGE_ME message received by a node.

This method processes the MERGE_ME message, which indicates a forced merge between the sender and the receiver. It triggers the merge and updates the node’s state accordingly.

on_min_link_weight(node: MMNode, message: Message)

Handles the event when a minimum link weight message is received by a node.

This method processes the received message, updates the node’s state, and determines the next steps based on the node’s role in the tree (root or non-root).

on_notification(node: MMNode, message: Message)

Handles the notification message received by a node.

This method processes a notification message, updates the node’s city, and manages the parent-child relationships within the node’s tree structure. It also sends the notification to the node’s children and triggers any necessary actions when the city changes.

partial_termination(node)

Handles the partial termination of a node in the Mega Merger algorithm.

This method sets the status of the given node to NOT_ELECTED and sends a termination message to all its children nodes.

Partial termination means that the node is not elected as the downtown node and neither it nor its children will make any further progress in the algorithm.

send_let_us_merge(node, new_city, road_weight)

Sends a ‘LET_US_MERGE’ message from the given node to its link with the minimum weight.

This method handles both border and internal nodes. For border nodes, it checks if the minimum weight of the node matches the provided road weight before sending the message. If the weights do not match, an error is logged and the method returns without sending the message. For internal nodes, it sends the message directly.

when_city_change(node, new_city, to_ask_min_weight)

Handles the event when a node’s city changes.

This method resets the node’s metadata and processes blocked messages related to merging and external status checks. Depending on the new city’s level and the message’s city level, it either merges the node with the source of the message or marks the source as internal or external.

Internal Processors: - let_us_merge_processor: Processes messages with the header LET_US_MERGE. - are_you_outside_processor: Processes messages with the header ARE_YOU_OUTSIDE.

If to_ask_min_weight is True, the node’s status is set to COMPUTING_MIN_WEIGHTS, and it initiates the process to ask for the minimum weight from external links.