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.info("Hello, I'm a node")
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 -- Returns the closest preceding finger of an id with respect to the finger
164 -- table of the current node.
165 -- - id: the id to find
166 -- - return value: the closest preceding finger of that id
167 function closest_preceding_node(id)
169 for i = nb_bits, 1, -1 do
170 if is_in_interval(my_node.fingers[i].id, my_node.id + 1, id - 1) then
171 -- finger i is the first one before id
172 return my_node.fingers[i].id
177 -- Finds the successor of an id
178 -- id: the id to find
179 -- return value: the id of the successor, or -1 if the request failed
180 function find_successor(id)
182 if is_in_interval(id, my_node.id + 1, my_node.fingers[1]) then
183 -- my successor is the successor
184 return my_node.fingers[1]
187 -- ask to the closest preceding finger in my table
188 local ask_to = closest_preceding_node(id)
189 return remote_find_successor(ask_to, id)
192 -- Asks a remote node the successor of an id.
193 -- ask_to: id of a remote node to ask to
194 -- id: the id to find
195 -- return value: the id of the successor, or nil if the request failed
196 function remote_find_successor(ask_to, id)
198 local task = simgrid.task.new(comp_size, comm_size)
199 task[type] = "find successor"
200 task[request_id] = id
201 task[answer_to] = my_node.id
203 if task:send(ask_to, timeout) then
204 -- request successfully sent: wait for an answer
206 task = simgrid.comm.wait(my_node.comm_recv, timeout)
207 my_node.comm_recv = simgrid.task.irecv(my_node.id)
210 -- failed to receive the answer
213 -- a task was received: is it the expected answer?
214 if task[type] ~= "find successor answer" or task[request_id] ~= id then
215 -- this is not our answer
218 -- this is our answer
228 -- Asks a remote node its predecessor.
229 -- ask_to: id of a remote node to ask to
230 -- return value: the id of its predecessor, or nil if the request failed
231 function remote_get_predecessor(ask_to)
233 local task = simgrid.task.new(comp_size, comm_size)
234 task[type] = "get predecessor"
235 task[answer_to] = my_node.id
237 if task:send(ask_to, timeout) then
238 -- request successfully sent: wait for an answer
240 task = simgrid.comm.wait(my_node.comm_recv, timeout)
241 my_node.comm_recv = simgrid.task.irecv(my_node.id)
244 -- failed to receive the answer
247 -- a task was received: is it the expected answer?
248 if task[type] ~= "get predecessor answer" then
249 -- this is not our answer
252 -- this is our answer
253 -- FIXME make sure the message answers to this particular request
263 -- Checks the immediate successor of the current node.
267 local successor = my_node.fingers[1]
268 if successor ~= my_node.id then
269 candidate = remote_get_predecessor(successor)
271 candidate = my_node.predecessor
274 -- this node is a candidate to become my new successor
275 if candidate ~= nil and is_in_interval(candidate, my_node.id + 1, successor -1) then
276 my_node.fingers[1] = candidate
279 if successor ~= my_node.id then
280 remote_notify(successor, my_node.id)
284 -- Notifies the current node that its predecessor my have changed
285 -- - candidate_predecessor: the possible new predecessor
286 function notify(candidate_predecessor)
288 if my_node.predecessor == nil or is_in_interval(candidate_predecessor,
289 my_node.predecessor + 1, my_node.id - 1) then
290 my_node.predecessor = candidate_predecessor
294 -- Notifies a remote node that its predecessor my have changed.
296 -- - candidate the possible new predecessor
297 function remote_notify(notify_to, candidate_predecessor)
299 local task = simgrid.task.new(comp_size, comm_size)
300 task[type] = "notify"
301 task[request_id] = candidate_predecessor
302 task:dsend(notify_to)
305 -- Refreshes the finger table of the current node.
306 function fix_fingers()
308 local i = my_node.next_finger_to_fix
309 local id = find_successor(my_node.id + 2^i)
311 if id ~= my_node.fingers[i] then
314 my_node.next_finger_to_fix = (i % nb_bits) + 1
318 -- Checks whether the predecessor of the current node has failed.
319 function check_predecessor()
323 -- Performs a find successor request to an arbitrary id.
324 function random_lookup()
329 simgrid.platform(arg[1] or "../../msg/msg_platform.xml")
330 simgrid.application(arg[2] or "../../msg/chord/chord90.xml")