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 (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 simgrid.get_clock() < 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 simgrid.get_clock() >= next_fix_fingers_date then
74 -- Returns whether an id belongs to the interval [a, b[.
75 -- The parameters are noramlized to make sure they are between 0 and nb_keys - 1).
76 -- 1 belongs to [62, 3].
77 -- 1 does not belong to [3, 62].
78 -- 63 belongs to [62, 3].
79 -- 63 does not belong to [3, 62].
80 -- 24 belongs to [21, 29].
81 -- 24 does not belong to [29, 21].
82 function is_in_interval(id, a, b)
84 -- normalize the parameters
89 -- make sure a <= b and a <= id
101 -- Finds the successor of an id
102 -- id: the id to find
103 -- return value: the id of the successor, or -1 if the request failed
104 function find_successor(d)
106 if is_in_interval(id, my_node.id + 1, my_node.fingers[1]) then
107 -- my successor is the successor
108 return my_node.fingers[1]
111 -- ask to the closest preceding finger in my table
112 local ask_to = closest_preceding_node(id)
113 return remote_find_successor(ask_to, id)
116 -- Asks a remote node the successor of an id.
117 -- ask_to: id of a remote node to ask to
118 -- id: the id to find
119 -- return value: the id of the successor, or -1 if the request failed
120 function remote_find_successor(ask_to, id)
123 local task = simgrid.task.new(comp_size, comm_size)
124 task[type] = "find successor"
125 task[request_id] = id
126 task[issuer] = my_node.id
128 if task:send(ask_to, timeout) then
129 -- request successfully sent: wait for an answer
132 task = simgrid.comm.wait(my_node.comm_recv, timeout)
133 my_node.comm_recv = simgrid.task.irecv(my_node.id)
136 -- failed to receiver the answer
139 -- a task was received: is it the expected answer?
140 if task[type] ~= "find successor" or task[request_id] ~= id then
141 -- this is not our anwser
144 -- this is our answer
145 successor = task[answer_id]
155 -- Returns the closest preceding finger of an id with respect to the finger
156 -- table of the current node.
157 -- - id: the id to find
158 -- - return value: the closest preceding finger of that id
159 function closest_preceding_node(id)
161 for i = nb_bits, 1, -1 do
162 if is_in_interval(my_node.fingers[i].id, my_node.id + 1, id - 1) then
163 -- finger i is the first one before id
164 return my_node.fingers[i].id
169 simgrid.platform(arg[1] or "../../msg/msg_platform.xml")
170 simgrid.application(arg[2] or "../../msg/chord/chord90.xml")