1 -- A SimGrid Lua implementation of the Chord DHT
10 max_simulation_time = 1000
12 fix_fingers_delay = 120
13 check_predecessor_delay = 120
16 -- current node (don't worry, globals are duplicated in each process)
19 next_finger_to_fix = 1,
25 -- Main function of each Chord process
28 -- - the id of a guy I know in the system (except for the first node)
29 function node(my_id, known_id)
31 simgrid.debug("Hello, I'm a node with id " .. my_id .. " and I know " .. known_id)
35 if known_id == nil then
40 success = join(known_id)
46 local now = simgrid.get_clock()
47 local next_stabilize_date = now + stabilize_delay
48 local next_fix_fingers_date = now + fix_fingers_delay
49 local next_check_predecessor_date = now + check_predecessor_delay
50 local next_lookup_date = now + lookup_delay
53 my_node.comm_recv = simgrid.task.irecv(my_node.id)
55 while now < max_simulation_time do
57 task = simgrid.comm.test(node.comm_recv)
60 -- I received a task: answer it
61 my_node.comm_recv = simgrid.task.irecv(my_node.id)
64 -- no task was received: do periodic calls
65 if now >= next_stabilize_date then
67 next_stabilize_date = simgrid.get_clock() + stabilize_delay
69 elseif now >= next_fix_fingers_date then
71 next_fix_fingers_date = simgrid.get_clock() + fix_fingers_delay
73 elseif now >= next_check_predecessor_date then
75 next_check_predecessor_date = simgrid.get_clock() + check_predecessor_delay
76 elseif now >= next_lookup_date then
78 next_lookup_date = simgrid.get_clock() + lookup_delay
81 -- nothing to do: sleep for a while
82 simgrid.process.sleep(5)
85 now = simgrid.get_clock()
93 -- This function is called when the current node receives a task.
94 -- - task: the task received
95 function handle_task(task)
97 local type = task.type
99 if type == "find successor" then
101 -- is my successor the successor?
102 if is_in_interval(task.request_id, my_node.id + 1, my_node.fingers[1]) then
103 task.type = "find successor answer"
104 task.answer = my_node.fingers[1]
105 task:dsend(task.answer_to)
107 -- forward the request to the closest preceding finger in my table
108 task:dsend(closest_preceding_node(task.request_id))
111 elseif type == "get predecessor" then
112 task.answer = my_node.predecessor
113 task:dsend(task.answer_to)
115 elseif type == "notify" then
116 -- someone is telling me that he may be my new predecessor
117 notify(task.request_id)
119 elseif type == "predecessor leaving" then
122 elseif type == "successor_leaving" then
125 elseif type == "find successor answer" then
128 elseif type == "get predecessor answer" then
132 error("Unknown type of task received: " .. task.type)
136 -- Returns whether an id belongs to the interval [a, b[.
137 -- The parameters are normalized to make sure they are between 0 and nb_keys - 1.
138 -- 1 belongs to [62, 3].
139 -- 1 does not belong to [3, 62].
140 -- 63 belongs to [62, 3].
141 -- 63 does not belong to [3, 62].
142 -- 24 belongs to [21, 29].
143 -- 24 does not belong to [29, 21].
144 function is_in_interval(id, a, b)
146 -- normalize the parameters
151 -- make sure a <= b and a <= id
163 -- Attemps to join the Chord ring.
164 -- - known_id: id of a node already in the ring
165 -- - return value: true if the join was successful
166 function join(known_id)
168 local successor = remote_find_successor(known_id, my_node.id)
169 if successor == nil then
173 my_node.finger[1] = successor
177 -- Returns the closest preceding finger of an id with respect to the finger
178 -- table of the current node.
179 -- - id: the id to find
180 -- - return value: the closest preceding finger of that id
181 function closest_preceding_node(id)
183 for i = nb_bits, 1, -1 do
184 if is_in_interval(my_node.fingers[i].id, my_node.id + 1, id - 1) then
185 -- finger i is the first one before id
186 return my_node.fingers[i].id
191 -- Finds the successor of an id
192 -- id: the id to find
193 -- return value: the id of the successor, or -1 if the request failed
194 function find_successor(id)
196 if is_in_interval(id, my_node.id + 1, my_node.fingers[1]) then
197 -- my successor is the successor
198 return my_node.fingers[1]
201 -- ask to the closest preceding finger in my table
202 local ask_to = closest_preceding_node(id)
203 return remote_find_successor(ask_to, id)
206 -- Asks a remote node the successor of an id.
207 -- ask_to: id of a remote node to ask to
208 -- id: the id to find
209 -- return value: the id of the successor, or nil if the request failed
210 function remote_find_successor(ask_to, id)
212 local task = simgrid.task.new("", comp_size, comm_size)
213 task.type = "find successor"
215 task.answer_to = my_node.id
217 if task:send(ask_to, timeout) then
218 -- request successfully sent: wait for an answer
220 task = simgrid.comm.wait(my_node.comm_recv, timeout)
221 my_node.comm_recv = simgrid.task.irecv(my_node.id)
224 -- failed to receive the answer
227 -- a task was received: is it the expected answer?
228 if task.type ~= "find successor answer" or task[request_id] ~= id then
229 -- this is not our answer
232 -- this is our answer
242 -- Asks a remote node its predecessor.
243 -- ask_to: id of a remote node to ask to
244 -- return value: the id of its predecessor, or nil if the request failed
245 function remote_get_predecessor(ask_to)
247 local task = simgrid.task.new("", comp_size, comm_size)
248 task.type = "get predecessor"
249 task.answer_to = my_node.id
251 if task:send(ask_to, timeout) then
252 -- request successfully sent: wait for an answer
254 task = simgrid.comm.wait(my_node.comm_recv, timeout)
255 my_node.comm_recv = simgrid.task.irecv(my_node.id)
258 -- failed to receive the answer
261 -- a task was received: is it the expected answer?
262 if task.type ~= "get predecessor answer" then
263 -- this is not our answer
266 -- this is our answer
267 -- FIXME make sure the message answers to this particular request
277 -- Checks the immediate successor of the current node.
281 local successor = my_node.fingers[1]
282 if successor ~= my_node.id then
283 candidate = remote_get_predecessor(successor)
285 candidate = my_node.predecessor
288 -- this node is a candidate to become my new successor
289 if candidate ~= nil and is_in_interval(candidate, my_node.id + 1, successor -1) then
290 my_node.fingers[1] = candidate
293 if successor ~= my_node.id then
294 remote_notify(successor, my_node.id)
298 -- Notifies the current node that its predecessor my have changed
299 -- - candidate_predecessor: the possible new predecessor
300 function notify(candidate_predecessor)
302 if my_node.predecessor == nil or is_in_interval(candidate_predecessor,
303 my_node.predecessor + 1, my_node.id - 1) then
304 my_node.predecessor = candidate_predecessor
308 -- Notifies a remote node that its predecessor my have changed.
310 -- - candidate the possible new predecessor
311 function remote_notify(notify_to, candidate_predecessor)
313 local task = simgrid.task.new("", comp_size, comm_size)
315 task.request_id = candidate_predecessor
316 task:dsend(notify_to)
319 -- Refreshes the finger table of the current node.
320 function fix_fingers()
322 local i = my_node.next_finger_to_fix
323 local id = find_successor(my_node.id + 2^i)
325 if id ~= my_node.fingers[i] then
328 my_node.next_finger_to_fix = (i % nb_bits) + 1
332 -- Checks whether the predecessor of the current node has failed.
333 function check_predecessor()
337 -- Performs a find successor request to an arbitrary id.
338 function random_lookup()
343 simgrid.platform(arg[1] or "../../msg/msg_platform.xml")
344 simgrid.application(arg[2] or "../../msg/chord/chord90.xml")