Browse Prior Art Database

ON THE POSSIBILITY AND IMPOSSIBILITY OF ACHIEVING CLOCK SYNCHRONIZATION

IP.com Disclosure Number: IPCOM000148563D
Original Publication Date: 1984-Mar-09
Included in the Prior Art Database: 2007-Mar-30
Document File: 24 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Dolev, Danny: AUTHOR [+3]

Abstract

RJ 4218 (46296) 3/9/84 REVISED 9/20J84 Computer Science

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 24

RJ 4218 (46296) 3/9/84 REVISED 9/20J84

Computer Science

Research Report

READING ROOM

~ O ~ ~ ~
SCIENCE DEpAiri.~b:r YALE UNIVEHSI'TY

ON THE POSSIBILITY AND IMPOSSIBILITY OF ACHIEVING CLOCK SYNCHRONIZATION
Danny Dolev
Hebrew University, Givat Ram
91904 Jerusalem, Israel
Joseph Y. Halpern

\ He Raymond Strong
IBM Research Laboratory

.' San Jose, CA 95193

This reDor1 bas been subm~cred for oubllcallon ours~de of l3hl and wlil probably be Copyughleo II acceoted for puol~cal~on 11 nas been Issued as a Researcn 6teoort for early dISSemlnallOn of 11s contents lo vlew of the lransler of copvrl~hl

10 Ihe oulslde publisher 11s dlSlr1bu1Ion Ovlstde of lBM orlor 10

~ ~ S l ~ c a l t o n
should be 11rn.led lo peer iommuntcatlons ana soeclf c ieauesls Atler ouls,de vublfcalion reauesls should be filled only
Ov reorfnts or eaally oblatnea cooles of tme arftcle le g

. Payment of -oyailtesl

-- - -

--- - - ----
- -
--

---

- - ---- Research Division

- - - ----

,-,

..

. ,

- Yorktown Heights, New York San Jose, California 8 Zurich, Switzerlznd

[This page contains 1 picture or other non-text object]

Page 2 of 24

Copies rndy be requested from
1BM Thomas J. LVarson Research Center Oistr~bution

         Services Post Off~ce

        Box 218
Yorktowrl i-le~ghrs.
New York 1G598

[This page contains 1 picture or other non-text object]

Page 3 of 24

RJ 4218 (46296) 3/9/84 REVISED 9/20/84 Computer Science

ON THE POSSIBILITY AND 1h.IPOSSIBILITY OF ACHIEVING CLOCK SYNCHRONIZATION*

Danny Dolev


Hebrew University, Givat Ram 9 1904 Jerusalem, Israel

Joseph Y. Halpern
H. Raymond Strong


IBM Research Laboratory,
San Jose, CA 95 193

ABSTRACT: It is known that clock synchronization can be achieved in the presence of faulty processors as long as the nonfaulty processors are connected, provided that some authentication technique is used. Without authentication the number of faults that can be tolerated.has been an open question. Here we show that if we restrict logical clocks to running within some linear function of real time, then clock synchronization is impossible without authentication when one-third or more of the processors are faulty. However, if there is a bound on the rate at which a processor can generate messages, then we show that clock synchronization is achievable, without authentication, so long as the nonfaulty processors are connected. Finally, we provide a Iower bound on the closeness to which simultaneity can be achieved in the network as a function of the transmission and processing delay properties of the network.

*A preliminary version of this paper appeared in the Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computation, Washington, D.C.,

1954 and as IBM RJ 4218.

[This page contains 1 picture or other non-text object]

Page 4 of 24

[This page contains 1 picture or other non-text object]

Page 5 of 24

1. INTRODUCTION

    The problem of achieving cl...