voula@utcsri.UUCP (Voula Vanneli) (02/28/85)
UNIVERSITY OF TORONTO
DEPARTMENT OF COMPUTER SCIENCE
ACTIVITIES FOR THE WEEK COMMENCING MARCH 4, 1985
(_S_F = _S_a_n_d_f_o_r_d _F_l_e_m_i_n_g _B_u_i_l_d_i_n_g, _1_0 _K_i_n_g'_s _C_o_l_l_e_g_e _R_o_a_d)
THEORETICAL ASPECTS SEMINAR - Thursday, March 7, 4 p.m., SF 1105
Dr. Cynthia Dwork
Laboratory for Computer Science, M.I.T.
9 "The Distributed Firing Squad Problem"*
Abstract
Most synchronous distributed algorithms assume that all
processors begin processing simultaneously. In an actual
distributed system, in which different transactions and
algorithms may be executed periodically, this may be unreal-
istic. Typically, an algorithm is executed in response to a
request from a specific processor, which may in turn be
responding to some external request. If the given processor
is correct then all correct processors learn of the request
simultaneously, so they can indeed begin the algorithm in
unison. However, if the processor is faulty then the
correct processors may learn of the request at different
steps. In this talk the design assumption of simultaneous
starts will be justified. Specifically, algorithms for the
associated synchronization problem, called the _d_i_s_t_r_i_b_u_t_e_d
_f_i_r_i_n_g _s_q_u_a_d problem, will be presented for a variety of
failure models. Matching lower bounds will also be
presented.