Clarification

This is a research report I wrote for Openmesh in January 2024. I worked as a software architect and designed the whole decentralised architecture for the Xnode overlay network, as well as supporting other research projects and providing some suggestions for the succeeding development process.

Please be aware that this is just the raw version of the initial architectural design, and the content may be outdated, buggy, or not accurate.

Link to the original post: https://blog.openmesh.network/raw-research-exploring-a-decentralized-microservice-architecture-for-xnode-946600b7d50a

Initial Project Plan Structure

The Decentralized Microservice Architecture of Xnode

Operating as a microservice, each Xnode contributes to the network by offering computational power and storage, and participating in essential processes like data verification and consensus maintenance

Short Project Description

This project aims to give a high-level description of the design and structure of Xnode, demonstrate its design philosophy, and also provide instructions and suggestions for its design and development process.

Intuition

• Mathematics problem.
• Count the number of occurrences for all numbers in nums.
• Specify the operation based on the number of occurrences.

Approach

The number of operations required to remove a specific number of occurrences can be found as follows:

1. Create an empty map count.
2. Initialise ans to 0.
3. Count the number of occurrences for every number in nums, and store it in count.
4. Use the table above to calculate the number of operations needed.
5. Return ans.

Pseudocode of minOperations():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

minOperations():
	Input nums an array of integers
	Output minimum number of operations to make array empty
	
	count = empty map
	ans = 0
	for all num in nums do
		if num not in count then
			count[num] = 1
		else
			count[num] += 1
		end if
	end for
	for all (key, value) in map do
		if value == 1 then
			return -1
		end if
		ans += celi(value / 3)
	end for

Introduction

aNode is initially a solution to challenge 3 of the OpenD/I Hackathon organised by Openmesh. The original requirements of this challenge are as follows (from the original OpenD/H Hackathon documentation):

1. Develop a solution that is able to receive data from multiple sources. It should be scalable to over 100 sources.

2. The solution should process this data in real-time. It should be saved to a database and transmitted to all listeners of a WebSocket.

3. A frontend should be present that gives insight into the current status of all components of your solution.

4. The solution should be able to support both REST API and WebSocket sources.

5. It should be easy to automatically deploy the solution. A containerized application (using for example docker) could be used or a setup script to handle installation could be provided.

Harnessing the power of the Gossip protocol, aNode redefines cloud infrastructure with its decentralised, resilient, and scalable architecture. It not only meets all the requirements above but also moves a step further: it’s completely decentralised, P2P, and suitable for both Web2 applications and Web3 dApps.

Understanding the Gossip Protocol

The Gossip protocol, often likened to the way rumors and gossips spread in social networks, is the basic of aNode. This protocol stands out for its robustness and simplicity in transmitting information across a cluster. Unlike traditional distributed consensus protocols that rely on centralised coordination systems (like Zookeeper and Etcd), the Gossip protocol operates on a more dynamic and decentralised principle, just like members of a community sharing news with their immediate neighbors.

At its core, the Gossip protocol involves nodes (i.e., aNode instances) periodically exchanging data with a randomly selected set of other nodes. This method ensures rapid and efficient transmission of data, which lets the information quickly reach all corners of the network. This approach offers several key advantages, particularly in cloud infrastructure:

1. High Scalability: As networks grow, the Gossip protocol naturally adapts, maintaining efficiency regardless of the size of the network. This makes aNode exceptionally scalable, an essential feature for modern cloud infrastructure.
2. Fault Tolerance: Unlike centralized systems, there is no single point of control or failure in decentralised systems based on the Gossip protocol. This network is also unstructured, which means the system is high availability and partition tolerance (comply with AP in the CAP theorem).
3. Efficiency in Bandwidth Usage: The protocol is cost-efficient, as it doesn’t require all nodes to communicate with a central server, reducing the likelihood of bottlenecks and enabling aNode to maintain high performance even under heavy load.
4. Self-Healing and Maintenance: The continuous exchange of information allows the network to constantly update and correct itself, ensuring that the system remains in a healthy state, which is crucial for cloud infrastructures that require high availability and reliability.

Intuition

• Traverse the left subtree.
• Visit the root node.
• Traverse the right subtree.

Approach 1: Recursion

• Implement the traversal process recursively.

Pseudocode of this approach:

1
2
3
4
5
6
7
8
9
10
11

path[]
traverse(root):
	Input root of a binary tree
	
	if root = NULL then
		return
	end if
	traverse(left(root))
	add root to path
	traverse(right(root))
	return

Complexity

Time complexity: $O(n)$.

Intuition

• Dynamic programming (bottom-up approach).
• Based on hint 1 (divide the corridor into segments):
  • There will be no solution if the number of seats is odd.
  • Divide corridor into multiple groups; each group contains exactly two seats and several plants.
• Based on hint 3 (if there are k plants between two adjacent segments, there are k + 1 positions (ways) you could install the divider):
  • There will be nbOfPlants + 1 ways to install a divider between two successive groups.
  • nbOfPlants is the number of plants between two successive groups (i.e., ignore the plants inside a single group).
• The answer is the number of ways to place a divider between each successive group times with each other.
• Define the answer as long to prevent potential overflows.

Approach

• Initialise nbOfSeats and nbOfPlants to 0, and initialise ans to 1 (assume that there are at least two seats in the corridor).
• Range over corridor (say corridor[i] as c):
  • Increase nbOfSeats if c is a seat.
  • If c is a plant:
    • Increase nbOfPlants if we have already found a group (nbOfSeats == 2).
    • Otherwise, the plant is inside a single group, and we should ignore it.
  • After reaching the start of the next group (nbOfSeats == 3):
    • Update ans.
    • Set nbOfSeats to 1 (i.e., move to the next group of seats), and clear nbOfPlants.
• Return 0 if nbOfSeats != 2 (i.e., there’s an odd number of seats).
• Otherwise, return ans.

Pseudocode of numberOfWays():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

numberOfWays(corridor):
	Input corridor a string that contains only 'S's and 'P's
	Output number of ways to install dividers in this corridor
	
	nbOfSeats = 0
	nbOfPlants = 0
	ans = 1
	for every c in corridor:
		if c == 'S':
			nbOfSeats++
		else:
			if nbOfSeats == 2:
				nbOfPlants++
		end if
		if nbOfSeats == 3:
			ans = (ans * (nbOfPlants + 1)) % (1e9 + 7)
			nbOfSeats = 1
			nbOfPlants = 0
	end for
	if nbOfSeats != 2:
		return 0
	end if
	return ans

Complexity

• Time complexity: $O(n)$.

  • $n$ iterations to calculate the answer.

• Space complexity: $O(1)$.

Intuition

• Check how many 1 bits are there in the binary representation of n.
• Using the right shift operation, check whether the last bit of n is 1 (by checking whether n is odd).

Approach

1. Initialise ans to 0.
2. While n is greater than 0 (i.e., the binary representation contains at least one 1 bit):
   1. Increase ans if the last bit of n is odd (i.e., the binary representation of n is 1).

Pseudocode of hammingWeight():

1
2
3
4
5
6
7
8
9
10

hammingWeight(n):
	Input n a 32-bit unsigned integer
	Output number of 1 bits in the binary representation of n
	
	ans = 0
	while n > 0:
		ans += (n % 2)
		right shift n
	end while
	return ans

Complexity

• Time complexity: $O(logn)$.

  • $logn$ iterations to calculate how many 1 bits are in the binary representation.

• Space complexity: $O(1)$.

Intuition

• Pairing the biggest number with the smallest number leads to the minimum pair sum for the biggest number.
• Remove them from the array, find the next biggest and smallest number, and pair them.
• Find the maximum pair sum while pairing and return it after the array is empty.

Approach

1. Sort nums in ascending order.
2. Initialise ans with 0, which represents that the maximum pair sum in nums is 0.
3. Iterate over nums from 0 to nums.size() / 2 - 1.
4. On each iteration:
   1. Pair nums[i] with nums[nums.size()-1-i].
   2. Calculate their pair sum and update ans.
5. Return ans.

Pseudocode of this problem:

1
2
3
4
5
6
7
8
9
10
11

minPairSum(nums):
	Input nums array of positive integers of size n
	Output the minimized maximum pair sum
	
	sort nums in ascending order
	ans = 0
	for all i from 0 to n / 2:
		// Pair nums[i] (the minimum number) with nums[n-1-i] (the maximum number)
		ans = max(ans, nums[i] + nums[n-1-i])
	end for
	return ans

Complexity

Time complexity: $O(nlogn)$.

Approach 1: Recursive

Intuition

• Since the maximum possible length of nums is $2^{16} = 65536$, which is not so big. As a consequence, it’s possible to solve this problem recursively.
• During the recursion, we can either choose from adding a zero "0" or adding a one "1" to the string.
• Try generating a unique string of length

Approach

1. Convert nums to a set unique.
2. Try generating a string from an empty string s:
   1. Try adding a zero ("0") to the end of s.
   2. If adding a zero is not possible (i.e., the string after adding a zero is a member of unique), try adding a one ("1").
   3. If the length of s euqals to nums.size() and s is not a member of unique, then return s.
   4. Otherwise, return an empty string.

Pseudocode of this approach:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

generate(s, maxLen, unique):
	Input s a string of length l
		maxLen the maximum length of s
		unique a set that contains all unique strings that can't be used
	Output a unique string of length maxLen
	
	if len(s) == maxLen:
		if s is not a member of unqiue:
			return s
		else:
			return empty string
		end if
	end if
	
	zero = generate(s + "0", maxLen, unique)
	if zero is not an empty string:
		return zero
	else:
		return generate(s + "1", maxLen, unique)
	end if

findDifferentBinaryString(nums):
	Input nums array of unique binary strings
	Output a unique binary string that not contains in nums
	
	unique = empty set
	for every string s in nums:
		add s to unique
	end for
	return generate("", nums.size(), unique)

Complexity

Link to this problem

HackerRank Extra Long Factorials

Intuition

• Implement large number multiplication using a string or an array.

Approach

1. Create an array called largeInteger, which represents a large number.
2. Fill the largeInteger with n.
3. Iterate over numbers from n to 0:
   1. Multiply largeInteger by this number.
   2. Handle the potential carry.
4. Output the content of largeInteger to stdout.

Pseudocode of largeIntMultiply:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

largeIntMultiply(largeInt, n):
	Input largeInt a very large number represent by an array
		n the multiplier
	Output the largeInt multiplied by n
	carry = 0
	for every i from largeInt.size()-1 to 0:
		number = n * largeInt[i] + carry
		largeInt[i] = number % 10
		carry = number / 10
		if i == 0 and carry != 0:
			add a 0 at the beginning of largeInt
			i++
		end if
	end for
	return largeInt

Intuition

• Find the first and last occurrence (say firstOccurrence and lastOccurrence) of an unused character c.
• Count the number of unique characters between firstOccurrence and lastOccurrence (including c itself).

Approach

1. Create an empty set visited.
2. For every character c in s:
   1. If c is a member of visited, jump to the next character.
   2. Otherwise, find the firstOccurrence and lastOccurrence of c in s.
   3. Create an empty set unique.
   4. Add every character between firstOccurrence and lastOccurrence to unique.
   5. Add the size of unique to answer.

Pseudocode of countPalindromicSubsequence:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

countPalindromicSubsequence(s):
	Input string s
	Output number of unique palindromic subsequences in s of length 3
	
	visited = empty set
	ans = 0
	for every character c in s:
		if c in set:
			continue
		end if
		add c to visited
		firstOccurrence = -1
		lastOccurrence = -1
		for every i from 0 to s.length():
			if firstOccurrence == -1:
				firstOccurrence = i	// Ensure that firstOccurrence only updates once
			end if
			lastOccurrence = i
		end for
		unique = empty set
		for every i from firstOccurrence + 1 to lastOccurrence:
			add s[i] to unique
		end for
		ans += unique.size()
	end for
	return ans

Complexity

• Time complexity: $O(n)$.
  • At most $\Sigma = 26$ iterations of outer loop.
  • In each iteration:
    • Find firstOccurrence and lastOccurence is $O(n)$.
    • Create unique set is $O(n)$.
  • Overall complexity is $O(\Sigma n) = O(n)$.
• Space complexity: $O(\Sigma)$.
  • s only contains lowercase English letters, so $\Sigma = 26$.
  • As a consequence, the maximum size of visited and unique is 26.