Module: Politics::DiscoverableNode

Defined in:
lib/politics/discoverable_node.rb

Overview

A module to solve the Group Membership problem in distributed computing. The “group” is the cloud of processes which are replicas and need to coordinate. Handling group membership is the first step in solving distributed computing problems. There are two issues: 1) replica discovery 2) controlling and maintaining a consistent group of replicas in each replica

Peer discovery is implemented using Bonjour for local network auto-discovery. Each process registers itself on the network as a process of a given type. Each process then queries the network for other replicas of the same type.

The replicas then run the Multi-Paxos algorithm to provide consensus on a given replica set. The algorithm is robust in the face of crash failures, but not Byzantine failures.

Instance Attribute Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#coordinator ⇒ Object

Returns the value of attribute coordinator.



39
40
41
 
# File 'lib/politics/discoverable_node.rb', line 39

def coordinator
  @coordinator
end

#group ⇒ Object

Returns the value of attribute group.



38
39
40
 
# File 'lib/politics/discoverable_node.rb', line 38

def group
  @group
end

Instance Method Details

#find_replicas(count) ⇒ Object 



54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/politics/discoverable_node.rb', line 54

def find_replicas(count)
  replicas.clear if count % 5 == 0
  return if count > 10 # Guaranteed to terminate, but not successfully :-(

  #puts "Finding replicas"
  peer_set = []
  bonjour_scan do |replica|
    (his_rid, his_peers) = replica.hello(rid)
    unless replicas.has_key?(his_rid)
      replicas[his_rid] = replica
    end
    his_peers.each do |peer|
      peer_set << peer unless peer_set.include? peer
    end
  end
  #p [peer_set.sort, replicas.keys.sort]
  if peer_set.sort != replicas.keys.sort
    # Recursively call ourselves until the network has settled down and all
    # peers have reached agreement on the peer group membership.
    sleep 0.2
    find_replicas(count + 1)
  end
  Politics::log.info { "Found #{replicas.size} peers: #{replicas.keys.sort.inspect}" } if count == 0
  replicas
end

#hello(remote_rid) ⇒ Object

Called for one peer to introduce itself to another peer. The caller sends his RID, the responder sends his RID and his list of current peer RIDs.



83
84
85
 
# File 'lib/politics/discoverable_node.rb', line 83

def hello(remote_rid)
  [rid, replicas.keys]
end

#register(group = 'foo') ⇒ Object 



41
42
43
44
45
46
47
48
 
# File 'lib/politics/discoverable_node.rb', line 41

def register(group='foo')
  self.group = group
  start_drb
  register_with_bonjour(group)
  Politics::log.info { "Registered #{self} in group #{group} with RID #{rid}" }
  sleep 0.5
  find_replicas(0)
end

#replicas ⇒ Object 



50
51
52
 
# File 'lib/politics/discoverable_node.rb', line 50

def replicas
  @replicas ||= {}
end

#rid ⇒ Object

A process’s Replica ID is its PID + a random 16-bit value. We don’t want weigh solely based on PID or IP as that may unduly load one machine.



89
90
91
92
93
 
# File 'lib/politics/discoverable_node.rb', line 89

def rid
 @rid ||= begin
   rand(65536) + $$
  end
end