High availability is a cornerstone of fault tolerance in production clusters. The following article delves into the novel methods and models to achieve rapid cluster leader failover based on the Replica State Discovery Protocol (RSDP). Firstly, RSDP is described and evaluated as a method of achieving consensus within homogenous multiagent distributed systems. This paper provides a novel mathematical model that describes the internal procedure of the said protocol. Additionally, diagrams and algorithm steps are provided to further simplify integration of the RSDP into modern Decentralized Coordination Networks (DCNs). Secondly, a new state reducer is developed that allows to perform a synchronized leader election process. Its mathematical model and code implementation written in JavaScript are provided and comply with an established extension interface described within the confines of Evaluation and implications of the newly created leader election protocol are provided to further expand the horizons of DCN coordination. Lastly, this article explores the practical implications of the mentioned state reducer in the context of the stateful cluster leader failover. Three different approaches and models based on the proposed consensus algorithm to mitigate spontaneous critical events are modeled and assessed. Based on failure probability, failover duration, and communication overhead mathematical models, the said approaches were compared, and recommendations for their application were provided. Overall, this article is aimed at further development of RSDP and describes novel approaches towards relevant coordination issues inside the clusters with high demands for availability and fault tolerance.
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
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 [
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 [
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. logically. That is especially problematic during wartime or a nation-wide crisis.
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 [
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 [
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 [
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.
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 [
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 [
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 [
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 [
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 [
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. [
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 [
RSDP has its own dedicated article that describes every operation, state change, and
consensusoriented process in detail [
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 [
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.
• • replica .
is denoted as S(T→AT)US( ) from to .
During the initiation, each replica Upon receiving H( E)LLO, a replica current state .
H( E)LLO from H( E)LLO to all other replicas.
S(T→AT)US( ) containing its ∀ ∈ ℛ, state agg. The aggregation function agg =
combines individual states: ( { ∣∣ S(T→AT)US( ) received} )
Where is a function that removes references to from . ← ( , { agg ∣ ( ) ∣ SHARE ( a(gg)) received} )
( )
→
C( L)OSE ∀ ∈ ℛ ∖ { }, ← ( , )
Define as a set of possible states for a replica. Each state may include: Membership list ⊆ ℛ; Resource utilization ∈ ℝ+;
Other reducer and application-specific data. • • • • • • • •
The aggregation function ( ) combines multiple states:
∈ ℳ = { HELLO, STATUS, SHARE, CLOSE} × Payload ({ 1, 2, . . . , }) = ⋃ Reducerk({ 1, 2, . . . , })
For membership lists: agg = ⋃ ; For resource utilization agg = |{ 1, 2,..., }| ∑ . 1 The state update function updates the local state based on received aggregated states: ← ( , { a1gg, a2gg, . . . , a(gg)})
Updating membership lists: ← ⋃ a(gg);
protocol, particularly during state updates. ” is used during critical sections of the 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. • • • • • • • • • • • •
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 [
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.
= { 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.
Method • • = ∅; = ⊥ (temporarily undefined).
( ), as an input, accepts a list of status messages status = [ S1TATUS, S2TATUS, … , STATUS], where each STATUS contains a sender address STATUS.address∈ . During its execution it performs the following operations: Extract addresses: ′ = { STATUS.address∣ = 1,2, … , }; 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:
true if L′ = isLeader {false if L′ ≠
Method aggregateShareState(shareMessageBuffe)r expects a list of share messages ℎ = [ S1HARE, S2HARE, … , SHARE], where each STATUS replicaMembers currentLeader Below are multiple approaches to aggregate the state components replicaMembers currentLeader • •
Select last message: last = SHARE;
a. ′ = last.replicaMember,s b. ′ = last.currentLeader.
As result returns replicaMembers= ′, currentLeader= ′. rather than relying on the latest and could be described as follows: assigning points from each of the participants. Consider a set of share messages defined as the ℎ = [ S1HARE, S2HARE, … , SHARE], where ∀ ∈ ℎ contains a ranked list of replica members = [ ,1, ,2, … , , ], where = | | be the number of candidates in , with ,1 being the most desired leader and , being the least desired leader.
For each message ∈ ℎ .
o For each candidate , at position in compute the weight , = 2 − . Initialize a score set = { ,1, ,2, … , , }, where , = 0 for = 1,2, … , .
For each candidate , : o Update the candidate's score , ← , + , ; • • • • • • •
Let ℋ = ∅ be a multiset of hashed state components.
For each message ∈ ℎ : • Extract state components: o = .replicaMember;s o = .currentLeader. • Form state tuple:
o = ( , ). • Compute hash of the state tuple:
o ℎ = ℎ( ), where ℎ is a hash function. • Add ℎ to ℋ:
o ℋ ← ℋ ∪ {ℎ }.
Identify the hash ℎ∗ with the highest frequency in ℋ:
o ℎ∗ = arg max(frequency(ℎ , ℋ)).
Find ∗ = ( ′, ′) such that ℎ( ∗) = ℎ∗.
As result returns replicaMembers= ′, currentLeader= ′. • • • • • • • • • • •
o
Let ∈ be the total score, where is a set of total scores for each candidate, then for , ∈ , = ∑ =1 =1 δ , , , ⋅ , ;
∑ where δ , , , is the Kronecker delta function: ▪ , , , { 1 if , = , 0 if , ≠ , o Identify the candidate ′ with the highest total score arg max( ) ∈ 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 .
Method leader ′ ∈ .
As result returns replicaMembers= ′,
currentLeader= ′. ℎ ( , ) expects a set ′ ⊆ and a Validate Members: areValidMembers= ( ′ ≠ ∅) ∧ ( self ∈ ′);
Validate Leader: isLeaderValid= ′ ∈ ′.
(areValidMembers∧ isLeaderValid) ⟹ {replicaMember:s ′,currentLeader: ′}; ¬(areValidMembers∧ isLeaderValid) ⟹ ∅.
Method ℎ
(
, ) expects ′ ⊆ and ′ ∈ .
Compare Members: membersChanged= ( ′ ≠ ); Compare Leader: leaderChanged= ( ′ ≠ );
Determine Reload Necessity: shouldReload= membersChanged∨ leaderChanged.
Method updateStat(ereplicaMember,scurrentLeader) 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
Otherwise it expects a list of close messages CLOSE has sender address CLOSE.address∈ .
= [ C1LOSE, C2LOSE, … , CLOSE], where each Extract Closing Addresses: Acl = { Update Replica Members: ← ∖ Acl; Recalculate Leader: ← max( ) if ≠ ∅ else ⊥.
CLOSE.address∣ = 1,2, … , };
Different approaches towards implementation of aggregateShareState(shareMessageBuffe)r 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.
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.
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.
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.
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)tp 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)tp + d = 2d + (n − 1)tp and since there are − 1 replicas sending “STATUS” messages, processing them takes ( − 1) .
Subsequently, the total “DEBATES” phase time ( DEBATES) is:
TDEBATES = 2d + (n − 1)tp + (n − 1)tp = 2d + 2tp(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:
TSHARE = d + (n − 1)tp Hence, the total time to reach consensus ( consensus) is:
Tconsensus= TDEBATES + TSHARE = (2d + 2tp(n − 1)) + (d + (n − 1)tp)
= 3d + 3tp(n − 1) = 3 ( + tp(n − 1))
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. 132 (2) (3)
• • • • •
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:
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:
Having the total amount of required messages to successfully achieve consensus, the probability that a replica successfully sends and receives all messages:
Pmsg = 1 − pl
Mtotal = 3(n − 1) = 3n − 3
Preplica = (1 − pf) × (Pmsg)Mtotal Consequently, the probability that all replicas will successfully participate is:
n
Pall replicas= (Preplica) = [(1 − pf) × (1 − pl)3n−3]n
Then the probability of consensus failure for the first election method: and considered in the following way: majority:
Plast state failure= 1 − [(1 − pf) × (1 − pl)3n−3]n
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 Let be the minimum number of replicas required for consensus (the quorum). For a simple q = ⌈ ⌉ 2 n k=q n k
Pquorum consensus= ∑ ( ) (Preplica)k(1 − Preplica) n−k
Pvote failure= 1 − Pquorum consensus
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. (4) (5) (6) (7) (8) (9) (10) (11)
A stateful cluster in the context of this article is a distributed system where each node has its own
subset of the system state. The subset might be either a unique unknown portion for every other
cluster member or, as a more common case, a subset of anot
establish a leader-follower model to achieve high consistency [
While the entire cluster follows a single leader, it becomes a single point of failure. The principles
of fault tolerance in that context require establishing a failover mechanism as a contingency. During
luster nodes should be probed and tested to detect
any issues promptly. As soon as the critical event on the leader node is detected, the mechanism
switches to the active phase of achieving consensus. The entire network has to agree upon a new
leader of a cluster to continue its operation [
The following list includes common definitions used to model every subsequent failover method and their properties: • • • • • • • • • • • • : Number of instances in the cluster. : Number of external observers (Method 2 & 3). ℎ: Health-check interval between instances (Method 1). ℎ : Health-check interval by observers (Methods 2 and 3). : Failure detection time. : Time to perform the failover procedure. : Consensus achieving time (an independent parameter). : Probability of an instance failing during the observation window. : Probability of an observer failing during the observation window. consensus: Probability of failure in achieving consensus. : Total observation time.
: Average size of a message (in bytes)
Each node/observer sends ( − 1) ( − 1) messages three times during consensus. In the following subsection, each failover topology will be described in terms of failover delay, total failure probability, and communication overhead. as an optimization phase to avoid going through the entire consensus cycle every time a node leaves the cluster.
We will first evaluate a model based on a single logical plane. Each node in such a cluster is
responsible for operational execution, monitoring, and governance. In such topology, every node
must have a communication link with every other in the system to successfully achieve consensus
and monitor other instances [
The cluster could be preconfigured to initiate health probes in a specified interval but with different initial timestamp shifts based on a node position in the network. This allows to efficiently utilize the repetitive status probes and decrease failure detection time. Additionally, since every node conducts the monitoring, the network can tolerate to up to – 1 failed nodes, where is a node set cardinality.
In that regard, LER provides all the necessary data needed to establish successful monitoring and election in an automated way. The capabilities of LER already provided data for the dynamic node discovery. Hence, every node has a list of the cluster members that they must probe. LER automatically adjusts the states of nodes in a cluster as soon as some subset leaves, but the new leader election cycle could also be triggered in case the nodes suffered critical events. E[Td1] = h 2N Tf1 = E[Td1] + Tc + Tp =
+ Tc + Tp h 2N Pall instances=
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:
The probability that all instances fail simultaneously ( all instance)s could be represented simply as an exponent of a single instance failure:
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: (12) (13) (14) (15) (16) (17) (18) instance sends consensus is:
Then the total failure probability 1 would be described in terms of consensus (Pconsensus) and all instances (Pall instance)s failure probabilities:
Pf1 = Pconsensus+ Pall instances− (Pconsensus× Pall instance)s
Mconsensus= N × (N − 1) × 3 The total number of messages exchanged during the observation period ( ) is:
h Mtotal1= (Tobs × Mhealth) + Mconsensus
Overhead1 = Mtotal1× Cm 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.
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 [
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: (19) (22) (23) ho
E[Td2] = 2
Tf2 = E[Td2] + Tp = h2o + Tp (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.
Pf2 = po + Pall instances− (po × Pall instance)s (21)
Moving on to the communication overhead model, the observer sends health checks to all instances. Messages per health-check interval ℎ :
Mhealth = N Then the total messages over observation time :
Mtotal2= Thoobs × Mhealth
Overhead2 = Mtotal2× Cm (24)
This model imposes smaller communication overhead and reduces coordination complexity but suffers from a single point of failure.
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 [
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: ho (25)
E[Td3] = 2M
Observers need to reach consensus after detecting a failure that takes . Then the total time from failure occurrence to failover completion:
Tf3 = E[Td3] + Tc + Tp = 2hMo + Tc + Tp (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:
Pf3 = Pconsensus+ Pall observers+ Pall instances− (Pconsensus× Pall observers× Pall instance)s Each of observers sends health checks to all instances. Then the Mhealth is:
Mhealth = M × N
Mconsensus= M × (M − 1) × 3 Then the total messages during
is: Mtotal3= (Tobs × Mhealth) + Mconsensus
ho Consequently, the communication overhead (Overhead3):
Overhead3 = Mtotal3× Cm (31)
This model provides a balance between communication overhead, complexity, separation of concerns and fault tolerance. (27) (28) (29) (30)
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 is 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.