clarke@utcsri.UUCP (Jim Clarke) (02/14/86)
(GB = Galbraith Building, 35 St. George Street)
(SF = Sandford Fleming Building, 10 King's College Rd.)
COLLOQUIUM, Tues., Feb. 25, 11 am, SF 1105
Professor C.C. Gotlieb
University of Toronto, DCS.
"Supercomputer Review"
SYSTEMS/THEORY/AI SEMINAR
Thurs., Feb. 27, 11 am, GB 220
Dr. Yoram Moses
M.I.T.
"Knowledge, Common Knowledge, and Simultaneous Actions
in the Presence of Faults"
(Abstract given below.)
NUMERICAL ANALYSIS SEMINAR, Thurs., Feb. 27, 3 pm, SF 1101
Professor T.E. Hull
University of Toronto, DCS.
"What can be expected of elementary functions?"
(Abstract given below.)
ABSTRACTS
Yoram Moses: "Knowledge, Common Knowledge, and Simultaneous Actions
in the Presence of Faults"
We show that any protocol that guarantees to perform a particular action
simultaneously at all sites of a distributed system must guarantee that the
sites attain common knowledge of particular facts when such an action is
performed. We analyze what facts become common knowledge at various points
in the execution of protocols in a simple model of a system in which pro-
cessors are liable to crash. We obtain a new protocol for Simultaneous
Byzantine Agreement that is optimal in all of its runs. That is, rather
than achieving the worst case behaviour, every run of the protocol halts at
the earliest possible time, given the pattern in which failures occur.
This may happen as early as after two rounds. We characterize precisely
what failure patterns require the protocol to run for k rounds, 1<k<t+2,
generalizing and simplifying the lower bound proof for Byzantine agreement.
We also show a non-trivial simultaneous action for which popular belief
would suggest that t+1 rounds would be required in the worst case, and use
our analysis to design a protocol for it that always halts in two rounds.
This work sheds considerable light on many heretofore mysterious aspects of
the Byzantine Agreement problem. It is one of the first examples of how
reasoning about knowledge can be used to obtain improved solutions to prob-
lems in distributed computing.
This is joint work with Cynthia Dwork of IBM Almaden.
T.E. Hull: "What can be expected of elementary functions?"
Scientific computing would be better off (e.g., in programming convenience,
portability, and proving correctness) if we had better standards. The
arithmetic is improving in this respect (e.g., IEEE), but more needs to be
done in related areas such as elementary functions and exception handling.
This talk is about what can be reasonably guaranteed about the elementary
functions (sqrt, exp, ln, arctan, sin, cos, ...) - both in fixed precision
and variable precision environments. Special attention will be given to
the exponential function.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,ihnp4,linus,utzoo}!utcsri!clarke