clarke@utcsri.UUCP (Jim Clarke) (10/29/85)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
THEORETICAL ASPECTS SEMINAR, Tues., Nov. 5, 4 pm, SF1105
Avi Wigderson
IBM Research, San Jose.
"Deterministic Simulation of Probabilistic
Constant Depth Circuits"
ARTIFICIAL INTELLIGENCE SEMINAR,
Wed., Nov. 6, 3 pm, Wallberg 116
Nils Nilsson
Stanford University
"Probabilistic Logic"
(Abstract at end of notice)
SYSTEMS SEMINAR, Thurs., Nov. 7, 11 am, SF1105
Professor Ozald Babaoglu
Cornell University
"Time-communication Tradeoffs for Reliable
Broadcast Protocols"
(Abstract at end of notice)
THEORETICAL ASPECTS SEMINAR, Thurs., Nov. 7, 4 pm, GB248
Benny Chor
Laboratory for Computer Science
M. I. T.
Title to be announced
ABSTRACTS
Nils J. Nilsson
Stanford University
"Probabilistic Logic"
Because many artificial intelligence applications require the ability to
reason with uncertain knowledge, it is important to seek appropriate gen-
eralizations of logic for that case. We present here a semantical general-
ization of logic in which the truth values of sentences are probability
values (between 0 and 1). Our generalization applies to any logical system
for which the consistency of a finite set of sentences can be established.
The method described in the present paper combines logic with probability
theory in such a way that probabilistic logical entailment reduces to ordi-
nary logical entailment when the probabilities of all sentences are either
0 or 1.
Ozald Babaoglu
Cornell University
"Time-communication tradeoffs for reliable
broadcast protocols"
We report results obtained in our study of the Reliable Broadcast problem
(Byzantine Agreement) time complexity as a function of communication net-
work properties. First, we formulate the problem in a system where the
underlying communication network supports broadcasts (such as Ethernets).
For this model of communication, we are able to obtain protocols that
achieve Reliable Broadcast in two rounds of message exchange, independent
of the failure model or the upper bound on the number of faulty processors.
We then consider the class of network structures characterized by their
diameter and their ability to support partial broadcasts. This class
includes fully connected point-to-point graphs, linear chains, rings,
broadcast channels and all other familiar communication structures. We
derive a protocol that implements Reliable Broadcast for any member within
this class where the execution time increases linearly with decreasing
broadcast degree and increasing diameter. The tradeoffs that are revealed
between performance, resiliency and network cost offer many new alterna-
tives previously not considered in designing fault-tolerant systems. (This
is joint work with Rogerio Drummond.)
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,ihnp4,linus,utzoo}!utcsri!clarke