The ultimate goal is to pack DAS in a node which allows users to use it as the basic element in a distributed network to solve hard problems. The idea is to use a connected network of DASNodes to split the effort of solving a hard problem. The goal of this task is to implement a basic simplified version of such node with only part of the features required to achieve the ultimate goal.
First, a little recap of the necessary concepts regarding distributed systems.
The fundamental building blocks that distributed systems employ to coordinate and communicate among network nodes are known as distributed primitives. These fundamental activities, or protocols, offer dependable and effective methods for exchanging information, coordinating actions, and managing errors in a distributed setting. A more complete list of such building blocks can be found here: https://en.wikipedia.org/wiki/Distributed_algorithm
Here, we list only the most relevant ones we need to implement DASNode.
Leader election
Reliable message exchanging
Atomic commit operations
Mutual exclusion in the use of shared resources
Consensus
Replication
Leader Election
A distributed system’s leader node is chosen using the leader election protocol to control coordination and decision-making. It’s frequently used in fault-tolerant systems to make sure that only one node is in charge of managing operations and making decisions. A leader election protocol can be used in a distributed system with numerous nodes to guarantee that one node is designated as the major node in charge of coordinating operations. Another node can be chosen as the new leader to take over the coordinating and decision-making duties if the primary node fails.
Reliable message exchanging
The nodes in the distributed system can communicate with each other in a reliable way no matter the geographical distribution of the Nodes (no assumption on connectivity can be taken other than the capability to use the predefined messaging protocol). Messages are guaranteed to be delivered. Messages from node A -> B are guaranteed to be delivered in the same order they have been issued. Messages can be exchanged between nodes deployed in different operational systems and running in different programming languages.
Atomic commit operations
An atomic commit is an operation where a set of distinct changes is applied as a single operation. If the atomic commit succeeds, it means that all the changes have been applied. If there is a failure before the atomic commit can be completed, the "commit" is aborted and no changes will be applied.
Mutual exclusion in the use of shared resources
Mutual exclusion strategies are not just a mean to prevent multiple agents from using a shared resource at the same time. Of course this is important but another very important aspect of such strategies is to make sure every agent have a fair chance to access the shared resources. In distributed systems lingo, it means to make sure that no agent will starve waiting for a resource.
Consensus
Consensus is a procedure that allows a group of nodes in a distributed system to agree on a common decision or understanding even when there are failures. Consensus methods guarantee that the agreed-upon value is trustworthy and consistent and that all nodes concur on it. More precisely, a Consensus protocol must satisfy the four formal properties below.
Termination: every correct process decides some value.
Validity: if all processes propose the same value V, then every correct process decides V.
Integrity: every correct process decides at most one value, and if it decides some value V, then V must have been proposed by some process.
Agreement: if a correct process decides V, then every correct process decides V.
Replication
To provide fault tolerance and scalability in a distributed system, replication is a strategy used to replicate data or services across several nodes. Through replication, it is made possible for another node to take over processing duties in the event of a failed node without affecting the system’s overall performance.
Basic implementation of DASNode
In this task we'll aim at implementing only a first simple use case. Basically we'll aim at "Leader election" and "Reliable message exchanging" as described above.
Use Case 1
USER: a person using the software we provide to execute JOBs in a network of NODEs.
NODE: a server process running on a Docker container encompassing all components required to run a DASNode.
JOB: a data structure designed to contain a script in one of the script languages supported by DASNode. This script contains all the code required to execute a given task.
MESSAGE: a data structure to encapsulate pieces of information we want to transport from one NODE to another.
Actions to be taken prior to the actual start of Use Case 1
USER starts manually each NODE in the network.
Each NODE is aware of all other NODEs.
All NODEs remain in a latent state waiting for JOB requests.
Actual Use Case 1
USER submit a JOB to any of the NODEs in the network.
NODE start processing the JOB. Eventually, other NODEs are contacted via MESSAGE exchanging to share the burden of processing the JOB.
Once the JOB finishes, results are collected by the same NODE originally contacted by the USER and delivered to the USER.
Non-functional requirements
Although Use Case 1 assumes a full-connected topology, other topologies must be considered when making message exchanging. Algorithms and data structures in DASNode must abstract the actual topology and work properly in any case. Priority is to support all the basic topologies e.g. ring, mesh, torus etc (see a mpore complete list here: https://en.wikipedia.org/wiki/Leader_election) but the goal is to support any arbitrary topology configured by the USER).
JOB should be defined as a script in some programming language. DASNode should be able to support multiple programming languages here so the design must be flexible. Initially we'll support only Python scripts doing queries to a remote DAS Server.
The messaging subsystem doesn't need to support cryptography in this stage but secure message exchanging is a must have in future versions, so the messaging subsystem architecture/design must at least take this into account making sure cryptography is doable without major rework.
NODEs must run inside Docker containers.
There's a TBD baseline JOB test case which will basically perform a single query to the remote DAS Server, process all the results and perform some extra computation on each result in order to evaluate each result's quality. The top N would be then delivered to the USER as the result of the JOB processing. This baseline test case should run with speedup of at least 70% * N considering the execution in a network with N (1 < N < 6) equally resourced NODEs against the execution in a single NODE.
We should have metainfo in NODEs and JOBs describing the capabilities of available hardware resources (NODEs) and a rough estimate of required resources per JOB or parts of the JOB
EPIC
This is required for https://github.com/singnet/das/issues/85
Introduction
The ultimate goal is to pack DAS in a node which allows users to use it as the basic element in a distributed network to solve hard problems. The idea is to use a connected network of DASNodes to split the effort of solving a hard problem. The goal of this task is to implement a basic simplified version of such node with only part of the features required to achieve the ultimate goal.
First, a little recap of the necessary concepts regarding distributed systems.
The fundamental building blocks that distributed systems employ to coordinate and communicate among network nodes are known as distributed primitives. These fundamental activities, or protocols, offer dependable and effective methods for exchanging information, coordinating actions, and managing errors in a distributed setting. A more complete list of such building blocks can be found here: https://en.wikipedia.org/wiki/Distributed_algorithm
Here, we list only the most relevant ones we need to implement DASNode.
Leader Election
A distributed system’s leader node is chosen using the leader election protocol to control coordination and decision-making. It’s frequently used in fault-tolerant systems to make sure that only one node is in charge of managing operations and making decisions. A leader election protocol can be used in a distributed system with numerous nodes to guarantee that one node is designated as the major node in charge of coordinating operations. Another node can be chosen as the new leader to take over the coordinating and decision-making duties if the primary node fails.
Reliable message exchanging
The nodes in the distributed system can communicate with each other in a reliable way no matter the geographical distribution of the Nodes (no assumption on connectivity can be taken other than the capability to use the predefined messaging protocol). Messages are guaranteed to be delivered. Messages from node A -> B are guaranteed to be delivered in the same order they have been issued. Messages can be exchanged between nodes deployed in different operational systems and running in different programming languages.
Atomic commit operations
An atomic commit is an operation where a set of distinct changes is applied as a single operation. If the atomic commit succeeds, it means that all the changes have been applied. If there is a failure before the atomic commit can be completed, the "commit" is aborted and no changes will be applied.
Mutual exclusion in the use of shared resources
Mutual exclusion strategies are not just a mean to prevent multiple agents from using a shared resource at the same time. Of course this is important but another very important aspect of such strategies is to make sure every agent have a fair chance to access the shared resources. In distributed systems lingo, it means to make sure that no agent will starve waiting for a resource.
Consensus
Consensus is a procedure that allows a group of nodes in a distributed system to agree on a common decision or understanding even when there are failures. Consensus methods guarantee that the agreed-upon value is trustworthy and consistent and that all nodes concur on it. More precisely, a Consensus protocol must satisfy the four formal properties below.
Replication
To provide fault tolerance and scalability in a distributed system, replication is a strategy used to replicate data or services across several nodes. Through replication, it is made possible for another node to take over processing duties in the event of a failed node without affecting the system’s overall performance.
Basic implementation of DASNode
In this task we'll aim at implementing only a first simple use case. Basically we'll aim at "Leader election" and "Reliable message exchanging" as described above.
Use Case 1
Actions to be taken prior to the actual start of Use Case 1
Actual Use Case 1
Non-functional requirements