8000 Initials · Marvin9/distributed-algorithms@4a00f0b · GitHub
[go: up one dir, main page]
Skip to content

Commit 4a00f0b

Browse files
Marvin9Marvin9
committed
Initials
0 parents  commit 4a00f0b

File tree

6 files changed

+245
-0
lines changed

6 files changed

+245
-0
lines changed

‎README.md

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
## Distributed algorithm
2+
3+
- A distributed algorithm is an algorithm, run on a distributed system, that does not assume the previous existence of a central coordinator.
4+
5+
### Election algorithms
6+
7+
- An election algorithm is an algorithm for solving the coordinator election problem. By the nature of the coordinator election problem, any election algorithm must be a distributed algorithm.
8+
-a group of processes on different machines need to choose a coordinator
9+
10+
> This repository contains basic simulation of bully-algorithm.
11+
12+
13+
[Reference](http://www2.cs.uregina.ca/~hamilton/courses/330/notes/distributed/distributed.html)

‎bully-algorithm/bully.go

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
package bully
2+
3+
import (
4+
"distributed-algorithms/utils"
5+
"fmt"
6+
)
7+
8+
// Start network simulation
9+
func (n *Network) Start() {
10+
n.Add(1)
11+
go n.bully()
12+
}
13+
14+
func (n *Network) ping(nodeID int) bool {
15+
for _, node := range n.Nodes {
16+
if node.NodeID == nodeID {
17+
if node.IsFailed {
18+
return false
19+
}
20+
return true
21+
}
22+
}
23+
return false
24+
}
25+
26+
func (n *Network) election(nodeIndex int) {
27+
utils.Debug(fmt.Sprintf("Node %v is holding election", n.Nodes[nodeIndex].NodeID))
28+
itr := nodeIndex - 1
29+
for itr >= 0 {
30+
// to get the feeling of distribution, I intentionally implemented verbose ping
31+
OK := n.ping(n.Nodes[itr].NodeID)
32+
if OK {
33+
utils.Debug(fmt.Sprintf("Node %v with high priority is up.", n.Nodes[itr].NodeID))
34+
// it's now upto Node[itr]
35+
n.election(itr)
36+
return
37+
}
38+
itr--
39+
}
40+
41+
// if no greater priority node are active
42+
n.MakeCoordinator(n.Nodes[nodeIndex].NodeID)
43+
}
44+
45+
func (n *Network) bully() {
46+
defer n.Done()
47+
totalNodes := len(n.Nodes)
48+
i := 0
49+
50+
for {
51+
n.Lock()
52+
utils.Debug(fmt.Sprintf("Node %v is in process", n.Nodes[i].NodeID))
53+
utils.Debug(n.Nodes)
54+
55+
if n.IsCoordinatorFailed() {
56+
utils.Debug("Coordinator node failed")
57+
n.election(i)
58+
}
59+
60+
i = (i + 1) % totalNodes
61+
n.Unlock()
62+
63+
var in string
64+
utils.Debug("Press i for input mode, c for continue...")
65+
fmt.Scanf("%s", &in)
66+
switch in {
67+
case "i":
68+
utils.Debug(n.Nodes)
69+
n.Controll()
70+
utils.Debug(n.Nodes)
71+
case "s":
72+
continue
73+
}
74+
}
75+
}
76+
77+
// Controll is used to make up and down nodes to feel the simulation and bully algorithm
78+
func (n *Network) Controll() {
79+
var nodeID NodeIDType
80+
var operation int
81+
fmt.Printf("\nEnter node Id and 0/1 to take that node down/up: ")
82+
fmt.Scanf("%d %d", &nodeID, &operation)
83+
84+
for idx := range n.Nodes {
85+
if n.Nodes[idx].NodeID == nodeID {
86+
if operation == 0 {
87+
n.Nodes[idx].IsFailed = true
88+
} else {
89+
n.Nodes[idx].IsFailed = false
90+
n.election(idx)
91+
}
92+
return
93+
}
94+
}
95+
}

‎bully-algorithm/modals.go

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
package bully
2+
3+
import (
4+
"distributed-algorithms/utils"
5+
"fmt"
6+
"sync"
7+
)
8+
9+
// NodeIDType is unique id for each node
10+
type NodeIDType = int
11+
12+
// PriorityType type of priority
13+
type PriorityType = int
14+
15+
// Node is instance of physical computer
16+
// with unique id, priority, is leader (currently running), failed or not
17+
type Node struct {
18+
NodeID NodeIDType
19+
CoordinatorNodeID NodeIDType
20+
Priority PriorityType
21+
IsCoordinator bool
22+
IsFailed bool
23+
}
24+
25+
// CreateNode - create new node
26+
func CreateNode(id NodeIDType, priority int) Node {
27+
return Node{
28+
id,
29+
-1,
30+
priority,
31+
false,
32+
false,
33+
}
34+
}
35+
36+
// Network is collection of node
37+
// where each node is able to discover all other nodes
38+
type Network struct {
39+
sync.WaitGroup
40+
sync.Mutex
41+
Nodes []Node
42+
Stop chan bool
43+
}
44+
45+
// CreateNetwork - init network
46+
func CreateNetwork() Network {
47+
return Network{
48+
Nodes: make([]Node, 0),
49+
Stop: make(chan bool),
50+
}
51+
}
52+
53+
// MakeCoordinator - will make one of node coordinator
54+
func (n *Network) MakeCoordinator(nodeID NodeIDType) {
55+
utils.Debug(fmt.Sprintf("Making Node %v coordinator", nodeID))
56+
for idx := range n.Nodes {
57+
if n.Nodes[idx].IsFailed {
58+
continue
59+
}
60+
n.Nodes[idx].CoordinatorNodeID = nodeID
61+
if n.Nodes[idx].NodeID == nodeID {
62+
n.Nodes[idx].IsCoordinator = true
63+
} else if n.Nodes[idx].IsCoordinator {
64+
n.Nodes[idx].IsCoordinator = false
65+
}
66+
}
67+
}
68+
69+
// InsertNode - insert node in network
70+
// insertion sort based on node priority
71+
func (n *Network) InsertNode(node Node) {
72+
totalNodes := len(n.Nodes)
73+
if totalNodes == 0 {
74+
n.Nodes = []Node{node}
75+
n.MakeCoordinator(node.NodeID)
76+
return
77+
}
78+
79+
n.Nodes = append(n.Nodes, node)
80+
itr := len(n.Nodes) - 2
81+
for itr >= 0 && n.Nodes[itr].Priority < node.Priority {
82+
n.Nodes[itr+1] = n.Nodes[itr]
83+
itr--
84+
}
85+
n.Nodes[itr+1] = node
86+
n.MakeCoordinator(n.Nodes[0].NodeID)
87+
}
88+
89+
// IsCoordinatorFailed - check the health of coordinator
90+
func (n *Network) IsCoordinatorFailed() bool {
91+
for _, node := range n.Nodes {
92+
if node.IsCoordinator && node.IsFailed {
93+
return true
94+
}
95+
}
96+
return false
97+
}

‎go.mod

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
module distributed-algorithms
2+
3+
go 1.15

‎main.go

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package main
2+
3+
import (
4+
"distributed-algorithms/bully-algorithm"
5+
)
6+
7+
func simulateBully() {
8+
network := bully.CreateNetwork()
9+
10+
nodes := []bully.Node{
11+
bully.CreateNode(1, 1),
12+
bully.CreateNode(2, 2),
13+
bully.CreateNode(3, 3),
14+
bully.CreateNode(4, 4),
15+
}
16+
17+
for _, node := range nodes {
18+
network.InsertNode(node)
19+
}
20+
21+
network.Start()
22+
network.Wait()
23+
}
24+
25+
func main() {
26+
simulateBully()
27+
}

‎utils/debug.go

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package utils
2+
3+
import (
4+
"fmt"
5+
)
6+
7+
// Debug - consistent debugging
8+
func Debug(msg interface{}) {
9+
fmt.Printf("\n%v\n", msg)
10+
}

0 commit comments

Comments
 (0)
0