Introduction

Being tasked with a complex design of a modern distributed system leads inevitably to the myriads of convoluted architecture decisions towards achieving high availability and fault tolerance. Throughout the entire history of computer science and Internet Technology industry, the cornerstone problem is threefold: consistency, availability, and partition tolerance, renown also as CAP theorem [1][2][3][4][5][6][7].

The theorem in its basis promotes an assumption that service could only be two of three: either consistent and available, available and tolerant to partitioning, or consistent and tolerant to partitioning [1][2][3][4][5][6][7]. Though it has to be stated that business-centric approaches produced variants of the said theorem that put resource utilization, complexity, and service quality instead while going through the decision-making process.

Nevertheless, the crux is the same; it is assumed that no model, method, approach, or methodology exists that could completely satisfy every property of this group. That assumption is still holding strong, since mechanisms that comply with one subset directly obstruct efforts of achieving the other [1][2][3][4][5][6][7].

It has been known throughout the history of research efforts into building reliable systems, that trying to achieve fault tolerance while relying on a single instance is futile. This can be attributed to the following reasons:

1. No matter how much the source code is being tested, extremely rare race conditions could still happen when dealing with external devices or even replicated systems. 2. Physical destruction of the datacenter will nullify any logical sound and fault-tolerant mechanism that was preliminarily implemented. 3. Even if we assume that software is logically consistent, a random radiation ray could flip some bits in the system and lead to a catastrophe. 4. logically. That is especially problematic during wartime or a nation-wide crisis. 5. At some point you will simply have to put the running instance under maintenance, and this will effectively stop its operation for a while.

While building cloud systems that require high availability, an architect has to eventually consider replication and clusterization techniques [8][9][10][11][12]. Within the context of this article, we will differentiate between these terminologies in the following way:

• Replication is a distributed topology of a homogeneous multiagent system, where each participants of the said network. Each replica may have the same set of initial parameters, program code, logic, and ongoing state. Therefore, replicated environments provide rapid disaster recoveries since every other instance could effectively take the responsibilities of the one that failed [8][9][10].

• Clusterization refers to the distributed system organization, where the overall state is still synchronized and coordinated but the purpose and the concurrent tasks on different nodes are different. The common purpose of building clustered systems is state splitting. Other examples may include hot and warm standby servers that replicate events from the main machine but still follow the orders from a leader and are usually restricted in their functionality [13][14][15].

Therefore, the purpose of this article is to model multiple approaches towards coordinating replicated and clustered decentralized networks. As a result of the conducted evaluation, a set of practical recommendations is proposed to simplify the decision-making process during the system design stage.

Additionally, it is the intent of this paper to develop a mathematical model for the Replica State Discovery Protocol, which serves as a framework for performing cluster-wide state synchronization and coordination. RSDP provides a basis upon which a set of logical extensions could be built to achieve various consensus effects.

Using the mentioned consensus basis, multiple leader election mechanisms were developed and modeled. Each of those mechanisms is characterized by a set of unique security, efficiency, and resilience properties, allowing for catering to the need of a specific environment. The said properties were compared based on probability and computational complexity assessments and as a result, recommendations for their application were provided.

Replica State Discovery Protocol

The fundamental problem in managing resilience through redundancy is coordination. Since the managed objects are by definition separated, they usually do not have any common memory location that would allow them to successfully establish a synchronization algorithm based on classical concurrency control mechanisms such as locks, mutexes, or semaphores [16][17][18].

There are quite a few solutions that allow for both immediate and eventually consistent consensus-achieving. An example of the first would be total order broadcast, or, in other words, complete replication of events in the original order. Eventually-consistent algorithms tend to take the process in steps to reach consensus regarding a proposed value. Examples of such algorithms include Raft, Paxos, Ring, ZooKeeper, and many others [19][20][21].

In that regard, the Replica State Discovery Protocol could be called one of the eventually consistent algorithms. RSDP provides not only the basis for achieving consensus but also serves as a distributed coordination framework, allowing for various extensions and handling cluster events. The difference between classical leader election or consensus-reaching protocols and RSDP is the intention and flexibility they provide. The former usually concentrate on the process of voting for a single common value. In the meantime, RSDP provides a foundation not only for single-state consensus but also for synchronizing complex state setups and merges [22].

Local Area Network Simulation based on AMQP

RSDP in its core was initially designed on the basis of the local area network simulation based on the Advanced Message Queuing Protocol. The details of its implementation, efficiency, security, implications, and resilience are outlined in a separate article. But for the purpose of theoretical context, a few words have to be said to cover potential questions regarding the reliability of RSDP and its message passing process [22].

First and foremost, the said network simulation is built on top of the message queueing protocol. In that context, AMQP stands as one of the most popular solutions in coordinating and routing complex message network topologies and is continuously gaining momentum in the field of research and engineering [23][24][25].

Figure 1 shows the conceptual operation basis of AMQP and its components: The fundamental idea of AMQP is the separation of client and server, which are called producer and consumer. Instead of direct communication, the message goes through the broker and its queue, thus allowing for alleviating direct dependency between clients and servers. Additionally, AMQP describes the achievement of fundamental communication properties such as resilience, durability, congestion control, security, etc. [23][24][25].

Local Area Network Simulation (SLAN) leverages these capabilities to establish a secure, resilient, and isolated LAN-like environment. In its basis, SLAN describes the provisioning of the two basic communication media: direct communication links and a broadcast link.

Figure 2 shows the interaction media of the SLAN: SLAN operation basis relies on the two main capabilities described within the context of AMQP:

binded queues (e.g., broadcast the message) or send the message to a single binded queue by the routing key (direct communication routing). AMQP defines the durability, mirroring, and quorum mechanisms for its queues and is considered to be a well-documented, tested, resilient, and flexible foundation for communication media. SLAN, and by implication, RSDP, rely on these properties to build its own abstraction layers [26,27].

RSDP phases and consensus process

RSDP has its own dedicated article that describes every operation, state change, and consensusoriented process in detail [22]. This section provides a succinct overview of RSDP phases with some amendments and clarifications for the operation sequences.

To provide capabilities of cluster-wide state operations, RSDP describes its lifecycle in a few phases is respectively responsible for the introduction of the new node, state sharing, and final state derivation. The last phase is responsible for handling the shutdown lifecycle event.

Since each distinct phase somehow interferes with the cluster state stored on each replica individually, every instance has a concurrency control mechanism based on the "𝑖𝑛𝑡𝑒𝑟𝑃ℎ𝑎𝑠𝑒𝑀𝑢𝑡𝑒𝑥". That mutex prevents multiple simultaneous cluster events from interfering with each other by restricting stored state access to a single active phase [16][17][18].

Figure 3 shows the phases and interaction during RSDP process: "𝑖𝑛𝑡𝑒𝑟𝑃ℎ𝑎𝑠𝑒𝑀𝑢𝑡𝑒𝑥" that prevents state mutation announcing its presence in the cluster. This message is sent through the broadcast channel and is meant to be received by all cluster members. replica would then buffer answers from the cluster members and perform an aggregation of the state as dictated by the state reducers. exchange to all the members. The final operation of the initial phase is to release the mutex and wait for any other cluster-wide events. cluster. Share messages would then be buffered for a configured amount of time to avoid redundant replica reloads. After the timeout elapses, the protocol engine would acquire the mutex, and the share messages would be validated and aggregated, giving a holistic view of the cluster-wide state. Subsequently, the protocol engine would release the mutex and wait for any other occurring events in the system. a replica goes down, it signals the others while others in the cluster would then first acquire the mutex, perform the necessary state updates, and release the mutex. No additional synchronization is necessary as the protocol assumes that every operation performed on the state is deterministic and made within the scope of a set of clean functions that do not rely on side effects.

RSDP mathematical model

Let ℛ = {𝑅 1 , 𝑅 2 , … , 𝑅 𝑛 } be the set of replicas in the distributed system. The replicas communicate over a network represented as a graph 𝐺 = (ℛ, 𝐸), where 𝐸 ⊆ ℛ × ℛ denotes the set of communication channels between replicas.

Each replica 𝑅 𝑖 maintains a local state 𝑆 𝑖 , which is an element of the global state space 𝒮. The global state of the system is a tuple 𝒮 = (𝑆 1 , 𝑆 2 , … , 𝑆 𝑛 ).

transitions. Remaining replicas adjust their states to reflect the departure:

•∀𝑅 𝑗 ∈ ℛ ∖ {𝑅 𝑖 }, 𝑆 𝑗 ← 𝑓 𝑐𝑙𝑜𝑠𝑒 (𝑆 𝑗 , 𝑅 𝑖 )

Where 𝑓 𝑐𝑙𝑜𝑠𝑒 is a function that removes references to 𝑅 𝑖 from 𝑆 𝑗 .

RSDP formal definition and properties

Define 𝒮 as a set of possible states for a replica. Each state 𝑆 𝑖 may include:

• Membership list 𝑀 𝑖 ⊆ ℛ; • Resource utilization 𝑈 𝑖 ∈ ℝ + ;

• Other reducer and application-specific data.

Define ℳ as the set of all possible messages: 𝑚 ∈ ℳ = {𝑚 HELLO , 𝑚 STATUS , 𝑚 SHARE , 𝑚 CLOSE } × Payload The aggregation function (𝑓 𝑎𝑔𝑔 ) combines multiple states:

𝑓 𝑎𝑔𝑔 ({𝑆 1 , 𝑆 2 , . . . , 𝑆 𝑗 }) = ⋃ Reducer k ({𝑆 1 , 𝑆 2 , . . . , 𝑆 𝑗 }) 𝑘

This could be defined as:

• For membership lists: 𝑀 agg = ⋃ 𝑀 𝑗 𝑗 ;

• For resource utilization 𝑈 agg = This may involve:

• Updating membership lists: 𝑀 𝑖 ← ⋃ 𝑀 agg (𝑘) 𝑘 ;

• Adjusting resource utilization estimates;

• Updating any other application-specific data.

To prevent race conditions, the "𝑖𝑛𝑡𝑒𝑟𝑃ℎ𝑎𝑠𝑒𝑀𝑢𝑡𝑒𝑥" is used during critical sections of the protocol, particularly during state updates.

Let μ 𝑖 be a mutex for replica 𝑅 𝑖 . Then, state updates are performed under the lock μ 𝑖 :

𝑆 𝑖 ← μ 𝑖 𝑓 𝑢𝑝𝑑𝑎𝑡𝑒 ({𝑆 1 , 𝑆 2 , . . . , 𝑆 𝑗 })

As was previously stated, RSDP is based on eventual consistency, where all replicas converge to the same state after a finite number of message exchanges.

For any two replicas 𝑅 𝑖 and 𝑅 𝑗 , their states 𝑆 𝑖 and 𝑆 𝑗 satisfy:

lim 𝑡→∞ Pr (𝑆 𝑖 (𝑡) = 𝑆 𝑗 (𝑡)) = 1

The protocol ensures that messages are eventually delivered, and state updates occur. If a message 𝑚 is sent from 𝑅 𝑖 to 𝑅 𝑗 , then 𝑚 will be delivered to 𝑅 𝑗 after some finite delay δ. In case some messages will be lost, RSDP defines repeatable synchronization sessions as a contingency.

Leader Election Reducer for the RSDP

storing, retrieving, validation, aggregating, and updating a state is defined in a set of preconfigured reducers. The original article of RSDP describes the benefits of such a modular approach. Additionally, it provides a thorough explanation of the interface that every reducer must follow to successfully integrate with the protocol. The list of defined methods includes [22]: Out of the mentioned methods, 𝑔𝑒𝑡𝐶𝑢𝑟𝑟𝑒𝑛𝑡𝑆𝑡𝑎𝑡𝑒 is the only method that is not required. This states. For example, discovery of replica members does not require 𝑔𝑒𝑡𝐶𝑢𝑟𝑟𝑒𝑛𝑡𝑆𝑡𝑎𝑡𝑒 implementation since this could be derived from the sender addresses.

• 𝑔𝑒𝑡𝐶𝑢𝑟𝑟𝑒𝑛𝑡𝑆𝑡𝑎𝑡𝑒:

Mathematical model of the leader election process

Leader election reducer is an extension that performs a replicated deterministic holistic decision on the trusted entity based on incoming cluster events. Having discussed the RSDP foundation and the basis for leader election reducer, let us define an abstract description of the consensus process.

Assume 𝑐

• 𝐴 = {𝑎 1 , 𝑎 2 , … , 𝑎 𝑛 }: the set of all replica addresses;

• 𝑎 self ∈ 𝐴: the address of the current replica instance, 𝑎 self = 𝑎 𝑐 ;

• 𝐺 𝑐 ⊆ 𝐴: the current set of replica members known to the replica;

• 𝐿 ∈ 𝐺 𝑐 : the address of the current leader.

Initially:

• 𝐺 𝑐 = ∅; • 𝐿 = ⊥ (temporarily undefined).

Method 𝑎𝑔𝑔𝑟𝑒𝑔𝑎𝑡𝑒𝑆𝑡𝑎𝑡𝑒(𝑠𝑡𝑎𝑡𝑢𝑠𝑀𝑒𝑠𝑠𝑎𝑔𝑒𝐵𝑢𝑓𝑓𝑒𝑟), as an input, accepts a list of status messages 𝑀 status = [𝑚 STATUS • Sort addresses: arrange 𝐺 ′ in ascending order according to a total order ( ≤) on addresses 𝐴, 𝐺 sorted = Sort(𝐺 ′ ); This operation could also include additional sorting criteria. • Determine leader: 𝐿 ′ = max(𝐺 sorted );

• Initialize state (if 𝐺 𝑐 is ∅ or 𝐿 is ⊥): 𝐺 𝑐 ← 𝐺 sorted , 𝐿 ← 𝐿 ′ .

As a result of its execution, the new state components are returned as the following tuple: replicaMembers = 𝐺 sorted , currentLeader = 𝐿 ′ .

Method 𝑛𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒𝑆𝑡𝑎𝑡𝑒(𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝐿𝑒𝑎𝑑𝑒𝑟) expects an 𝐿 ′ ∈ 𝐴 as an input and performs the following transformation: As result returns replicaMembers = 𝐺 ′ , currentLeader = 𝐿 ′ .

rather than relying on the latest and could be described as follows:

• Let ℋ = ∅ be a multiset of hashed state components. o In case of a tie, apply a deterministic tie-breaker, such as selecting the candidate with the highest address according to the total order ≤ on 𝐴.

As result returns replicaMembers = 𝐺 ′ , currentLeader = 𝐿 ′ . Method 𝑠𝑎𝑛𝑖𝑡𝑖𝑧𝑒𝑆ℎ𝑎𝑟𝑒𝑆𝑡𝑎𝑡𝑒(𝑟𝑒𝑝𝑙𝑖𝑐𝑎𝑀𝑒𝑚𝑏𝑒𝑟𝑠, 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝐿𝑒𝑎𝑑𝑒𝑟) expects a set 𝐺 ′ ⊆ 𝐴 and a leader 𝐿 ′ ∈ 𝐴.

• Validate Members: areValidMembers = (𝐺 ′ ≠ ∅) ∧ (𝑎 self ∈ 𝐺 ′ ); • Validate Leader: isLeaderValid = 𝐿 ′ ∈ 𝐺 ′ .

Output could be described then as:

• (areValidMembers ∧ isLeaderValid) ⟹ {replicaMembers: 𝐺 ′ ,currentLeader: 𝐿 ′ }; • ¬(areValidMembers ∧ isLeaderValid) ⟹ ∅.

Method 𝑠ℎ𝑜𝑢𝑙𝑑𝑅𝑒𝑙𝑜𝑎𝑑(𝑟𝑒𝑝𝑙𝑖𝑐𝑎𝑀𝑒𝑚𝑏𝑒𝑟𝑠, 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝐿𝑒𝑎𝑑𝑒𝑟) expects 𝐺 ′ ⊆ 𝐴 and 𝐿 ′ ∈ 𝐴. During its execution it performs the following operations:

• Compare Members: membersChanged = (𝐺 ′ ≠ 𝐺 𝑐 ); • Compare Leader: leaderChanged = (𝐿 ′ ≠ 𝐿); • Determine Reload Necessity: shouldReload = membersChanged ∨ leaderChanged.

Returns a Boolean that indicates whether a client should be notified about the state change. Method updateState(replicaMembers, currentLeader) expects a 𝐺 ′ ⊆ 𝐴 and 𝐿 ′ ∈ 𝐴. During its execution it performs: if (𝐺 ′ ≠ ∅ ∧ 𝐿 ′ ∈ 𝐺 ′ ) then (𝐺 𝑐 ← 𝐺 ′ , 𝐿 ← 𝐿 ′ ).

Method 𝑎𝑔𝑔𝑟𝑒𝑔𝑎𝑡𝑒𝐶𝑙𝑜𝑠𝑒𝑆𝑡𝑎𝑡𝑒(𝑐𝑙𝑜𝑠𝑒𝑀𝑒𝑠𝑠𝑎𝑔𝑒𝐵𝑢𝑓𝑓𝑒𝑟) depends on the implementation of a leader election function and whether it is completely deterministic. If the sorting is done with an inclusion of a locally asserted context, this method is supposed to trigger the initial phase of the RSDP to achieve consistency.

Otherwise Different approaches towards implementation of aggregateShareState(shareMessageBuffer) outlined in this section contribute to different properties of the election process. Method based on the latest source of truth is characterized by low computational intensity, but while reasonable in trusted and stable environments, is susceptible to network congestion or failures. This approach is not suitable for networks that have strict requirements for Byzantine fault tolerance.

Method based on a popular vote provides higher resilience for both intentional and unintentional discrepancies during the consensus process. It is a suitable approach for systems that are beset with an unstable or restricted environment. It is additionally characterized by increased computational complexity, though it could be reduced by taking into account only scalar values to avoid hashing overhead. This approach is the most resilient among the others against intentionally hostile behavior since, to perform an action, you have to gather the majority of votes.

Finally, the last method provides a solution based on the electoral points approach. It is the most stable and resilient option among the previous three in the context of unstable connections due to its ability to downgrade votes that have lost some portion of a state and hence have a limited view of the global state set. Though it is not resilient towards intentionally hostile actions since the state set cardinality could be superficially inflated.

Implementation of the leader election reducer

The following section describes practical implementation of the leader election reducer using JavaScript and the 𝐵𝑎𝑠𝑒𝑅𝑒𝑝𝑙𝑖𝑐𝑎𝑆𝑡𝑎𝑡𝑒𝑀𝑎𝑛𝑎𝑔𝑒𝑟𝑅𝑒𝑑𝑢𝑐𝑒𝑟 interface defined by the RSDP. The following algorithm assumes that every cluster member can trust the environment and implements the first approach from the previous section. Such an assumption is a common case when building coordinated replication between internal services to achieve high availability. From this point on we will refer Figure 4 shows the initial aggregation implementation logic: The initial state of the LER, as defined by the model, is comprised of an empty set of replica members and an undefined leader. This serves as an example of an abstract derived reducer subset since it does not have an initial 𝑔𝑒𝑡𝐶𝑢𝑟𝑟𝑒𝑛𝑡𝑆𝑡𝑎𝑡𝑒 to share with the cluster.

Method 𝑎𝑔𝑔𝑟𝑒𝑔𝑎𝑡𝑒𝑆𝑡𝑎𝑡𝑒 hence relies not on the data provided by the cluster members but on the messages themselves and their metadata. Its operation is simple; the new leader is defined as the replica that has the highest address. The sorting operation here is not redundant, since to achieve determinism, every node must have the same dataset and ordering. Subsequently, 𝑛𝑜𝑟𝑚𝑎𝑙𝑖𝑧𝑒𝑆𝑡𝑎𝑡𝑒 abstracts out the internal store and provides a simple answer to the client, whether he is a leader.

Figure 5 shows the share aggregation implementation logic: The 𝑠𝑎𝑛𝑖𝑡𝑖𝑧𝑒𝑆ℎ𝑎𝑟𝑒𝑆𝑡𝑎𝑡𝑒 method is responsible for verifying the consistency of the data received from the aggregated state. A leader is valid if it is in a set of known members, and the members are valid if it is not an empty set. Then, the 𝑠ℎ𝑜𝑢𝑙𝑑𝑅𝑒𝑙𝑜𝑎𝑑 method decides whether the state has changed and whether the client should be notified. At last, 𝑢𝑝𝑑𝑎𝑡𝑒𝑆𝑡𝑎𝑡𝑒 simply sets a new state if it was provided.

Figure 6 shows the close aggregation implementation logic: The 𝑎𝑔𝑔𝑟𝑒𝑔𝑎𝑡𝑒𝐶𝑙𝑜𝑠𝑒𝑆𝑡𝑎𝑡𝑒 Its primary goal is to deterministically determine a new set of cluster members and a leader. The leader election logic here is the same as during the initial aggregation. RSDP continuously resynchronizes the state of the cluster, so any discrepancies caused by the lost messages will eventually be resolved due to the principle of eventual consistency.

To conclude, RSDP provides a well-defined model for an arbitrary logical extension. The Farther research could lead to the different invariants of this protocol that could potentially be applicable in decentralized environments.

Leader election reducer duration and failure probability

Failure probability and consensus duration are two of the most important metrics for the consensusachieving algorithm. The following section provides mathematical models that describe these properties. We will start with a model of time required to reach a consensus. The following assumptions are made:

• Let 𝑛 be the total number of replicas in the system.

• Let 𝑑 be the maximum one-way network delay between any two replicas.

• Let 𝑡 𝑝 be the maximum time a replica takes to process a message.

• Phases to achieve initial consensus include "DEBATES" and "SHARE".

• All message delays and processing times are bounded and known.

• The SLAN layer provides guarantees of message delivery.

• The probability of the communication media coordinator failure is negligent.

DEBATES" phase each replica sends a "HELLO" message to all other replicas where time for a "HELLO" message to reach other replicas: 𝑑. After receiving a "HELLO" message, each replica processes it in time (n − 1)t p and sends back a "STATUS" message where time for a "STATUS" message to reach the original sender is 𝑑.

For a replica to receive "STATUS" messages from all others, the time is d + (n − 1)t p + d = 2d + (n − 1)t p and since there are 𝑛 − 1 replicas sending "STATUS" messages, processing them takes (𝑛 − 1)𝑡 𝑝 .

Subsequently, the total "DEBATES" phase time (𝑇 DEBATES ) is:

T DEBATES = 2d + (n − 1)t p + (n − 1)t p = 2d + 2t p (n − 1)(1

) During the "SHARE" phase, after aggregating the received "STATUS" messages, each replica broadcasts a "SHARE" message to all others. Time for "SHARE" message to reach other replicas is 𝑑. After that each replica processes incoming "SHARE" messages from 𝑛 − 1 replicas in time (𝑛 − 1)𝑡 𝑝 .

Then the total "SHARE" phase time (𝑇 SHARE ) is:

T SHARE = d + (n − 1)t p(2)

Hence, the total time to reach consensus (𝑇 consensus ) is:

T consensus = T DEBATES + T SHARE = (2d + 2t p (n − 1)) + (d + (n − 1)t p ) = 3d + 3t p (n − 1) = 3 (𝑑 + t p (n − 1))(3)

It is obvious then that the consensus achieving time is linearly dependent on the amount of cluster members. Additionally, network delay 𝑑 and processing time 𝑡 𝑝 are critical factors, but since the protocol is built on top of deterministic principles and clean functions, 𝑡 𝑝 should be negligent.

As for the failure probability, the following assumptions are made:

• Let 𝑝 𝑙 be the probability that a message is lost.

• Let 𝑝 𝑓 be the probability that a replica fails during the consensus process.

• Message losses and replica failures are independent.

• Each replica must receive "HELLO", "STATUS", and "SHARE" messages from all the replicas. • A replica successfully participates if it can send and receive all required messages.

The probability that a single message is successfully transmitted is:

P msg = 1 − p l(4)

During the consensus achieving stages, each replica must send 𝑛 − 1 "HELLO" and 𝑛 − 1 "SHARE" messages. Consequently, every replica expects to receive 𝑛 − 1 "HELLO", 𝑛 − 1 "STATUS", 𝑛 − 1 "SHARE" messages. Then the total messages received per replica could be represented as:

M total = 3(n − 1) = 3n − 3(5)

Having the total amount of required messages to successfully achieve consensus, the probability that a replica successfully sends and receives all messages:

P replica = (1 − p f ) × (P msg ) M total(6)

Consequently, the probability that all replicas will successfully participate is:

P all replicas = (P replica ) n = [(1 − p f ) × (1 − p l ) 3n−3 ] n(7)

Then the probability of consensus failure for the first election method:

P last state failure = 1 − [(1 − p f ) × (1 − p l ) 3n−3 ] n(8)

The probability of failure is dependent on key characteristics of the network and the underlying infrastructure. It is obvious that such an approach is suitable only in cases of stable network connections. SLAN layer provides delivery recovery mechanisms but does not solve every issue related to the message loss. Since the do not require successful participation of every node, the probability could be reevaluated and considered in the following way:

Let 𝑞 be the minimum number of replicas required for consensus (the quorum). For a simple majority:

q = ⌈ 𝑛 2 ⌉(9)

Consequently, the probability that at least 𝑞 replicas successfully participate is:

P quorum consensus = ∑ ( n k ) n k=q (P replica ) k (1 − P replica ) n−k (10)

Then the probability of consensus failure:

P vote failure = 1 − P quorum consensus (11) Evidently, vote-based approaches are significantly more resilient than the method based on the last state decision. In such systems, it is possible to withstand partial failure of participating nodes during the consensus process.

Figure 7 shows the topology of a self-regulated cluster of nodes: Each instance performs health checks on every other instance at intervals of ℎ. The expected time for the first instance to detect a failure is the minimum time any instance takes to detect it. Assuming health checks and uniformly distributed, the expected detection time is:

E[T d1 ] = h 2N(12)

After detecting failure, instances need to reach consensus. The consensus achieving time 𝑐 ) is considered an independent parameter to simplify the model and concentrate directly on the factors directly tied to the topology. The total time from failure occurrence 𝑇 𝑓1 to failover completion is the sum of detection time, consensus time, and failover procedure time:

T f1 = E[T d1 ] + T c + T p = h 2N + T c + T p(13)

The probability that all instances fail simultaneously (𝑃 all instances ) could be represented simply as an exponent of a single instance failure: P all instances = 𝑝 𝑖 𝑁 (14) Then the total failure probability 𝑃 𝑓1 would be described in terms of consensus (P consensus ) and all instances (P all instances ) failure probabilities: P f1 = P consensus + P all instances − (P consensus × P all instances )

Then each instance sends health checks to 𝑁 − 1 other instances. During consensus, each instance sends 𝑁 − 1 messages three times. The overall amount of the messages sent during consensus is:

M consensus = N × (N − 1) × 3(16)

The total number of messages exchanged during the observation period (𝑇 𝑜𝑏𝑠 ) is:

M total1 = ( T obs h × M health ) + M consensus(17)

Total communication overhead in bytes:

Overhead 1 = M total1 × C m(18)

the models that are tied directly to the system failover properties. But to achieve a holistic view, consensus time and maintenance time models must be included.

Centralized observer health monitoring

The topology with a centralized observer includes a set of stateful worker nodes in a cluster and a single coordinating machine that manages the entire network. This topology introduces the division between operational and control planes and thus fosters the single responsibility principle in the system [33,34].

Figure 8 shows the topology of a cluster monitored and coordinated by a single observer: Let us consider failure detection time 𝑇 𝑑2 . Assume that the observer performs health checks on all instances at intervals of ℎ 𝑜 . Then the expected time to detect a failure is half the health-check interval:

E[T d2 ] = h o 2(19)

Since there is no consensus process among instances, the total failover time is:

T f2 = E[T d2 ] + T p = h o 2 + T p(20)

The system relies on a single observer; its failure directly impacts the system's ability to perform failover. Probability of all Instances failing (𝑃 all_instances ) is the same as in the first method.

The total failure probability includes the observer failure and all instances failing:

P f2 = p o + P all instances − (p o × P all instances )(21)

Moving on to the communication overhead model, the observer sends health checks to all 𝑁 instances. Messages per health-check interval ℎ 𝑜 :

M health = N(22)

Then the total messages over observation time 𝑇 𝑜𝑏𝑠 :

M total2 = T obs h o × M health(23)

Consequently, the total communication overhead in bytes:

Overhead 2 = M total2 × C m(24)

This model imposes smaller communication overhead and reduces coordination complexity but suffers from a single point of failure.

Distributed observer health assessment

The following discussed topology is also comprised of two distinct execution plains. In such networks, a consensus algorithm is used between observers themselves and decides on the responsible node that must coordinate the workers plane [35][36][37].

Figure 9 shows the topology of a cluster monitored and coordinated by a group of observers: 𝑇 𝑑3 . With 𝑀 observers, the expected time to detect a failure is:

E[T d3 ] = h o 2M(25)

Observers need to reach consensus after detecting a failure that takes 𝑇 𝑐 . Then the total time from failure occurrence to failover completion:

T f3 = E[T d3 ] + T c + T p = h o 2M + T c + T p(26)

The probability that all observers fail simultaneously is 𝑃 all_observers = 𝑝 𝑜 𝑀 . Given that the of all instances failing (𝑃 all_observers ) is the same as in the previous methods, the total failure probability (𝑃 𝑓3 ) is: P f3 = P consensus + P all observers + P all instances − (P consensus × P all observers × P all instances )

Each of 𝑀 observers sends health checks to all 𝑁 instances. Then the M health is:

M health = M × N(28)

Additionally, each observer sends 𝑀 − 1 messages three times during consensus:

M consensus = M × (M − 1) × 3(29)

Then the total messages during 𝑇 𝑜𝑏𝑠 is:

M total3 = ( T obs h o × M health ) + M consensus(30)

Consequently, the communication overhead (Overhead 3 ):

Overhead 3 = M total3 × C m(31)

This model provides a balance between communication overhead, complexity, separation of concerns and fault tolerance.

Conclusions

Achieving consensus within the confines of a Decentralized Coordination Network based on homogenous multiagent system is a critical process that is gaining momentum in the research field due to the ever-growing sizes of distributed systems and requirements towards high availability. Within the context of this article, a novel leader election protocol was created and modeled based on the Replica State Discovery Protocol.

One of the primary goals of this article is to introduce a leader election state reducer as a logical extension of RSDP to address the rapid failover problem. As a result, multiple viable approaches were proposed towards building such a reducer that are based on different properties of common state aggregation. The first proposed method of leader election is based upon the supposition that the network is controlled, and fault tolerance against malicious action during consensus is not expected. That is a reasonable expectation since RSDP built on top of LAN simulation, which in turn is based on AMQP provider. Such providers often come with a set of authentication and authorization mechanisms of their own. This method is characterized by its low computational overhead and finality characteristics in case of an extremely dynamic network.

The following two methods are based on quorum approach towards handling the leader election process. The method based on a popular vote is the most suitable approach to ensure resilience against both intentional and accidental failures during consensus interactions. Popular vote is a common solution in networks that require Byzantine fault tolerance.

The third proposed leader election method based on RSDP, in its foundation relies on the weighted election algorithm. The approach is characterized by a greater degree of resilience in highly congested and unreliable networks where random packet losses occur frequently due to its ability of partial inclusion.

Given the mathematical models and graphs for the three different cluster failover models and approaches, it is fair to assume that none of those could be called objectively superior in every plain of comparison. Method involving self-regulated mutual health evaluation is most suitable when high additional infrastructure incurrence and the critical event detection time are the most influential metrics of the successful system operation. Though it is worth noting that the communication overhead grows exponentially with the number of cluster members.

The second method, based on centralized observer health monitoring, is an appropriate solution only in cases where higher infrastructure and communication overhead costs are a primary decision factor. Since the entire stability of the system depends on a single centralized external observer, the very same observer becomes a single point of failure, which could lead to a disaster when high availability is a hard requirement.

Lastly, a method based on distributed observer health assessment serves as a trade-off between high availability, infrastructure cost incurrence, communication overhead, and failover delay by offloading the decision-making process to the parallel distributed layer of coordination. Such an approach is mostly suitable for current cloud infrastructure demands due to its flexibility and clearly established separation of concerns.

Overall, this article aims to inspire a surge of further research in the complex, exciting, and extremely relevant field of distributed computing and management. The implications and results of this research allow to bolster the security of modern critical infrastructure by effectively describing novel ways of achieving resilience through redundancy and the distribution of responsibility. Provided mathematical and graphical models are provided to help in the complex decision-making process and reduce possible risks when choosing an appropriate model and approach for rapid cluster failover.