47:
process will compare the incoming UID to its own. If the UID is greater than its own UID then it will continue the message on. Otherwise if the UID is less than its own UID, it will not pass the information on. At the end of a phase, a process can determine if it will send out messages in the next round by if it received both of its incoming messages. Phases continue until a process receives both of its out messages, from both of its neighbors. At this time the process knows it is the largest UID in the ring and declares itself the leader.
164:
46:
The algorithm requires the use of unique IDs (UID) for each process. The algorithm works in phases and sends its UID out in both directions. The message goes out a distance of 2 hops and then the message heads back to the originating process. While the messages are heading "out" each receiving
233:
209:
146:
126:
106:
228:
202:
62:
60:; Sinclair, J. B. (November 1980), "Decentralized extrema-finding in circular configurations of processors",
195:
24:
40:
81:
142:
136:
122:
116:
102:
96:
179:
71:
28:
175:
57:
36:
222:
85:
32:
92:
171:
76:
163:
135:
Garg, Vijay K. (2002), "9.4 Hirschberg–Sinclair
Algorithm",
183:
101:, Morgan Kaufmann Publishers, Inc., pp. 482–483,
121:, Cambridge University Press, pp. 232–233,
203:
8:
141:, John Wiley & Sons, pp. 111–112,
210:
196:
75:
118:Introduction to Distributed Algorithms
7:
234:Algorithms and data structures stubs
160:
158:
95:(1996), "15.1.2 The HS Algorithm",
35:. It is named after its inventors,
182:. You can help Knowledge (XXG) by
14:
138:Elements of Distributed Computing
162:
1:
21:Hirschberg–Sinclair algorithm
250:
157:
63:Communications of the ACM
31:problem in a synchronous
16:Leader election algorithm
229:Distributed algorithms
178:-related article is a
98:Distributed Algorithms
77:10.1145/359024.359029
25:distributed algorithm
115:Tel, Gerard (2000),
191:
190:
58:Hirschberg, D. S.
241:
212:
205:
198:
166:
159:
151:
131:
111:
88:
79:
249:
248:
244:
243:
242:
240:
239:
238:
219:
218:
217:
216:
176:data structures
155:
149:
134:
129:
114:
109:
93:Lynch, Nancy A.
91:
70:(11): 627–628,
56:
53:
29:leader election
17:
12:
11:
5:
247:
245:
237:
236:
231:
221:
220:
215:
214:
207:
200:
192:
189:
188:
167:
153:
152:
147:
132:
127:
112:
107:
89:
52:
49:
41:J. B. Sinclair
37:Dan Hirschberg
15:
13:
10:
9:
6:
4:
3:
2:
246:
235:
232:
230:
227:
226:
224:
213:
208:
206:
201:
199:
194:
193:
187:
185:
181:
177:
173:
168:
165:
161:
156:
150:
148:9780471036005
144:
140:
139:
133:
130:
128:9780521794831
124:
120:
119:
113:
110:
108:9780080504704
104:
100:
99:
94:
90:
87:
83:
78:
73:
69:
65:
64:
59:
55:
54:
50:
48:
44:
42:
38:
34:
30:
27:designed for
26:
22:
184:expanding it
169:
154:
137:
117:
97:
67:
61:
45:
33:ring network
20:
18:
223:Categories
172:algorithms
51:References
86:15299430
145:
125:
105:
84:
170:This
82:S2CID
23:is a
180:stub
143:ISBN
123:ISBN
103:ISBN
39:and
19:The
174:or
72:doi
225::
80:,
68:23
66:,
43:.
211:e
204:t
197:v
186:.
74::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
