oa 

!	"#$%&		f	

			%! 	(&

Mahyar R. Malekpour 

Langley Research Center, Hampton, Virginia 
NASA STI Program . . . in Profile

"# )
&

###&#*+	"

#(,&
#

&	+-./(	 	+(%

$%(	&( 
+&

+(		,

&
.(	 	+(	"#	&

"(& %&.	+	,.

)	 )(	*#		&* )#

#+
0.,&
.(	 	+

(	*#&
	"#(

!#("	)&
&

1(		*	)&"(	*# &	 

	"#(.

&2	#,1"	("&#&


&#%
&
.1(	

	)2&&"#&2 	(	%(3

45
.6786..
,1(	

+(#		&	+9	 (&

		&&(	&	"


(	 	+#"#:*#	

&	%,."#+(

 #&##

	+#+#" 

		*",
"	(	(	

	*2#	+(	((	)"&* 

	 ++"	( &

#:	(&(	,

45
.641
!7,

#&# &	(	+	%	

(#	), ,);"$		(	)

2	$ ((	)# 	(&&

++,!:*

%,


11141,#

&# %
(	#

		#	,


'414
4786..
,#

((		+#&

	)%+()+	)	&	

+ (	#	(	#%
,

4.6786..
,)

&)	&		+	+


(	 	+)(	9)#+)

	#2&"9&* "

("	,

45
.61
6.
,4 &

 " 		 #

&+	(	
0+,

(#	*"#	 "+

&"	)"# "+##)#

	  #("& 		&	",

'	+		+"&
.

(	 	+)&2 3

&
.(	 	+&+( 

http://www.sti.nasa.gov

4+%"	;"*&.	

&(<,, *

':%"	;"&
.5(!$

=>>=

&&
.5(!$

=>>


?	3


.5(!$


			(.	+

>#	#!	*

5*	)!@=


	"#

(#+	

6 %1	&	

5+()A	 =@
BB



	






			oa 

!	"#$%&		f	

			%! 	(&

Mahyar R. Malekpour 

Langley Research Center, Hampton, Virginia 
*	+3


			(.	+

>#	#!	*

5*	)!@=


=>>


Acknowledgments 

&	2#"#"#	&%+?#%#"	& -/

	9
0*%(	 	+,&"&	2"#$&$&	*2		

&	#(&	*2#&("++,&"&	2"#$(%&$C	 

5 	&	"*++,

&"	#+	$	++""		&	(		"		(	 

##"#	+)&	:(	#	+(#)"&

(	#"	+""		%&
	"#(#+	,*

Abstract 

This report presents a deductive proof of a self-stabilizing distributed clock 

synchronization protocol. It is focused on the distributed clock synchronization of 

an arbitrary, non-partitioned digraph ranging from fully connected to 1-

connected networks of nodes while allowing for differences in the network 

elements. This protocol does not rely on assumptions about the initial state of the 

system, and no central clock or a centrally generated signal, pulse, or message is

used. Nodes are anonymous, i.e., they do not have unique identities. There is no 

theoretical limit on the maximum number of participating nodes. The only 

constraint on the behavior of the node is that the interactions with other nodes are 

restricted to defined links and interfaces. We present a deductive proof of the 

correctness of the protocol as it applies to the networks with unidirectional and 

bidirectional links. We also confirm the claims of determinism and linear 

convergence.
*

Table of Contents 

1. INTRODUCTION ..................................................................................................................................................1

2. SYSTEM OVERVIEW ..........................................................................................................................................2


,,!1.'14-/,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,


,
,546C.66D-LOCALTIMER/,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,=


,=,7
..
!46E-D) D)
!/,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,=


,,6CE-T/,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

3. THE PROTOCOL ..................................................................................................................................................5

=,,54C1551456!-TS/,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,@

=,
,E
4C4
!.A6.!.E,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

=,=,54
.1) 54E
51
.F41) 
!16'7
.
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

=,,167.
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

=,>,5446'8.6.F.
C!.1.874!6DE
51
.F.
1864,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

=,@,5446'8.6.F.
C!.1.874!6DE
51
.F.
16'118.11E!.C15,,,,,,B

4. A DEDUCTIVE PROOF OF THE CORRECTNESS OF THE PROTOCOL ...............................................10

5. CONCLUSIONS ...................................................................................................................................................22

REFERENCES ..........................................................................................................................................................23

APPENDIX A. SYMBOLS ......................................................................................................................................24


1. Introduction 

%&	 	&+		+  &"	"	#	 

++"#	"#%+,Synchronization#	"#%+&(	

achieving#maintaining"##$2+ #(#$,#	"#

%+# )	+			%)"	#	&

 ++"+#	+ +, +

2&	(	&%+	%&	%,& #	"#%+$

%&	(	+)&		)#*( 	&+-,,)(	/achieve#

maintain%&	%$#	"#%+	:(	 %+2#

#	"(&(	2	$++(	,&convergence#closure

(	(	##	&* #+ 2	$ %&	%)	(*%,5		&

	(	)2"&	+%&	+ $%&	

#	"#%+,

&	" &"#	# &%&	#	"#%+&(	*"*

	##,&+& #2&#	"#%&		&+(:%

#*( "#(	* &		&",.(&*

"&&	#(	*		","&")&2*	)$%(#	

"#(	%+,&(	(#"+"		%&	%#	##

(		:(	 %+2##	"(&(	2	$+

+(	#)	"		#	"#%+)&(	*	"","

#	2%++(	" 		GC	>HG	>H

G8"
H,.##)(	(#"+"(	*		,.+&+

(	#+##")++"+)&(	(#"+"&2		" 

*	++&#&;",'"	&	+	)##	 2	$++(	

	%+$"((	%+,

.G
H"(	#				%2	$-# 	(&/&

",&%+"#	"#%			%)(	## 	(&	  	+"%

##2	$#2&2 	#	&2	$

+,+2	$	"#	#)	 )"%#)(	)#	-&"/,

&"#	;"	%(	"		+2	+(& -, ,)

+## #	#( 			2	 /&2	$	#	&*%&	%,

&"+(";"*&"+(&"	

#,&#(	"		+"	(	*"2	$&8%:	+&"

(	"+G@H(	"&&"#&:	#2&&

8%",)" "&#			#&;")(

"%	#"&*	%"&%+,'"	&	+	)&

#  	&+"+	%&&		"&%+,

.&	(	2(	##"*(		&		+A Self-Stabilizing 

Distributed Clock Synchronization Protocol For Arbitrary DigraphsGH#+

#	++#	*	 &(	2&	(&(	#,

"##+#&(	2+#&$#%	+ &##

%+#	+%G8H,&+#&$ 	"&"##

+#&(	&**##&		&(	&%((%&

2	$2&"#	##	$,.##)&	"&*	+#&

+#	++#	*	 ,

&	(		 #2,.2(	*#%+*	*2,?(	&

(	##	(=,?(	##"*(	&		&

(	,?(	"# 	+	$>,

2. System Overview 

?#	%+(""(#-, ,)	)(+$	/(" 

(	#%	 "	+	*,&	#"(#&	" &+

(&%+-2			)&+(	)	2	%&	" &		*""+/&

2&+"&&	,?+#&%+#&	(	&

(""(##++"$&	(	&		*%,

&"#	% ( %#	#			%)(	## 	(&	  	+"%

##2	$KI#&:& + &	" &

++"$,
#	%+"),,)&%#&*";"#,#

	"+##),,)*%(	(&%&	(	#		%

:"&(	,&++"$	"+#2##,

++"$	"+##),,)	%		#	+&	"	#

&	##,&#++"2&&&	%:&  	#

+ ,8	#+ %#	#%	+ &+ )&+

+)#&	#	%#,&++"2	$#

 "	%	*	#			*	#+ &	* #)&)

#*	%	#	+ #	%	&+(		"

	#	&+ 	+GD(BBH,&	&		%+$	

:	%	#("	+ &2	$*,&++"$#

#&*			%(	*##&*"%&%+#&	&(	

"+(-=,/,

2.1. Drift Rate () 

4&##	*%#(#)		" (&%	-,,)&(&

	#%2%/# +$-,,)"	/)##LocalTimer)2&&

%$(	$&( +##	*%&(&%	,

oscillator tick)#clock tick	system tick)#	*"#&"

+&2	$G	>H,

#	&	#		2&	(	+)(	%+	$ &( 

+,1		&		#%	#		2&	(	+,&

	&#	"+#&*$2"###		))2&&+=

2&	(	+)2&	" *	*"#

	# JJ,&+:+"+#	&LocalTimer*	+	*t

*%-K/t,&+:+"+#	&2LocalTimer*	+	*t

 *%--K//t,&		)&maximum relative drift#

2&	(&&	*	+	*t*%&2 ;",

δ(t)L--K/-K//t-/

&" &	%"##% JJ)(	)"+#*	%

	,&"((	"#:*%#"#GH2&	2#	+#)

	&(	(	#&	(	)&"##% J,=*	

&	("	(,
*	&)&	&	(	)20"&	%(#

"#	),,) JJ,

2.2. The Logical Clock (LocalTimer) 

+

 





' "	,&LocalTimer,

&LocalTimer#	*%&(&%	)$#	*")#%

$(	$&( +,&2' "	)&LocalTimer+	

"	 	+*"+:+"+*",."		"(#)&LocalTimer

(	#%$ 	*"	+*"))+:+"+*")P)	%

	 2&&(	#)&")&LocalTimer"##%MLocalTimerMP,

2.3. Communication Delay (D, d, and ) 

' "	,4*	(#%)D)#2	$+(	)d,

&++"#%2#9#:(	#	+&++"+*

	(#%)D)#2	$+(	)d,&(	+		#	#2&&&(

' "	,#(#& "	)+ 	+#%#	+t0:(#

		*#	%##9#)(	#)#";"+ 

 	#%&&+	*Gt0KD)t0KDKdH,++"2

#(#%$##&	%+(	,&2	$+(	)d)&

+:+"++#	+ 	*	+ 	+	+ #2&

	(	+,&+(	#"&#	&	2&	(	

+)9	)#				)+(	"	##	& &&(&%

++"+#,&2(	+		"+#"##"&&D #

d #&&*"	+$$,&++"%)##)

:(	#	+D#d)###L-DKd/#&"	+$

$,&		)&++"#%2%2#9#"##%

G!)H,

2.4. Topology (T) 

++"$)	+(%$)# &	(&	(	 #	(&%

22#,(& 22# 

	+	$,(& &&"+	$ %2#,

&	( %)T)#	#	 %##	#	(&-# 	(&/ 

K#)2&	&##&	(&%$)&	(&	+

%#%&	#)#&$	&	"#		#	,'"	&	+	)

2"+&	#	$	+#),,)()#&		+"(

$#	% %2#%#	,

.&	(	)2"&	+2	$#	(&	& %,&2 	(&

(	+	"#&";",

2#	#adjacent&&		 &	&%	#

&&	*#	++"$,

L) 	*")&"+	$# &	 loop&	(&),,)&

+:+"+*"& (& &	+#$* &#

 &(&%-:(	&	#2&&&#/,

W) 	*")&"+	$ % &width	#+	&	(&)

,,)&+:+"+*"&&	(& %2#,

'	# 	(&KN)L#W	"##%MLMK#MWMK,>

3. The Protocol 

.&2"+	(	"+()(	(	)(	+	)##	&

(	("##,&		+&#	"#%&	(	+)S)

##%&2 ("(GH,

SL(K, T, D, d, , P, F)

.&	2	#)&#	"#%&	(	+"&"+	#-K/)

2	$( %-T/)*	(#%-D/)++"+(	-d/)	#	

	-/)%&	(	#-P/)#"+	"-F/)	(*%,&"&

(	+(	2&*	 #"	(	(	)++"+)#"#

";"%&,52*	)&(	(	#&	(	2##

2&")&"FL,

4&##	*%#(# +$)LocalTimer,&$#

(	#%%&	##"&	&	#	2&	(&&	,.	#	

&*%&	)&#++"%:&  Sync+ ,##

time out2&LocalTimer	&+:+"+*",7(+")&#	

2Sync+ #	#&	,##interrupted2&

(+ Sync+ 	LocalTimer	&&+:+"+*"),,)

	+",7(		"(#:(	(	##2#2-=,/)&#

	%&+ Sync+ %	# &	,

&(	#+%&		&* &%&	%			#&

resynchronization process2&	%#	  &%&	(	,&

	%&	(	 2&&	#+"#	+Sync+ #

#	&#	+Sync+ ,'	ρJJ)&#+"

 	&2#	+Sync+ GH,

Sync+ 	+#&		"	%&	+")	2&#

	*Sync+ -/#*&	#   &	%&	(	,

&+ #*	#&##	#(#++"$,

&2 ##	+	"#&#	(#(	&(	,

' "	="#&(2&&#	(,(	(	+	#&2	$*

+"	+		*"2&+#	+&* "	+$$,

52*	)%#&#*)(	+		#	,&#		

(	("	(2&+(+ &(	,

.	

'
#

2
#   

	. C"	# .   






1%&	

	

' "	=,1%&	(	#*	"(	,@

&resynchronization period)##P)&"	+$$#

##&"((	"#&+	*2%2"*	&

LocalTimer%#,

Drift per t)##δ(t))&"	+$$###&+:+"+

+"#	2%2#	&#"	t)δ(t) ,.(	"	3

!	(	D)##δ(D))	&#"	D)δ(D) ,

!	(	)##δ())	&#"	)δ() ,

!	(	P)##δ(P))	&#"	(	#P)δ(P) ,

&graph threshold)TS)#(#	(&( %#&"	

+$$,

&"	#(		+(%precision&2	$)##π)MπJP)&

"	+$$###&"	#&*(	+ 

#,

&convergence time)##C)&"	+$$###&

"#&+:+"++$	&2	$*	 ),,)&*

%&	%,

Precision between LocalTimers%2#9#Ni#Nj##%ij

#&"	+$$,

&initial synchrony&2	$#&	+2&&(	

+ #)"(*	 )2&π,& %&	%"	+

CInit,

&initial precision + LocalTimers###%Init)&"	

+$$#)	t  CInit)##+"	&(	&

2	$++#%		%&	(	,

&initial guaranteed precision+ LocalTimers###%

InitGuaranteed)&"	+$$#)	t  C)##+"	

&(	&2	$++#%		%&	(	,

3.1. The Graph Threshold (TS) 

?&#	*Sync+ ):(#"	 (	##2#2)(&Sync

+ )	LocalTimer#	%&Sync+ %	# &	,&

(	##2#22&	&# 	+ Sync+ )			#ignore 

window

)(	*#+	&(	(&#%	%&	

	 	#%&2"(Sync+ GH,?"#& 	2#2

G!)TS/,&2	"##"&++"+*	(#%)D)#&"((	"#)

			#&	(&&	&#)TS)"(#	(&( %,





&	+refractory period"# %(	#2	$# 	(	#+)2 &

+"	*)#"	 2&&&	*2	(##+"",

3.2. Sync Message And Its Validity 

.	#	&*%&	%)&#++"%:&  Sync+ 


,?&

&%+%&	%)&(	*	&#++ (		%&	

(	#P,"+ (&%%				#	#2&(	%)&	(

Sync+ #**#%&*"#+,&(	(		+##

2&&+ 	;"	+&+ 	+*	%#	#,52*	)&

")&	(Sync+ #**#%&*"#

+#+,*#Sync+ #	##		%#&%&		-

=,=/#&$(	$$,

3.3. The Monitor, The Synchronizer, And Protocol Functions 

#synchronizer#monitors,&&*	&	#)

#+(%+%+	&"+	##	%#2&

+		&"	+ + ,#&	"	+	2

+ ,+	$(	$&*		(# "	#,(%)

+		#)*")*#)#	&*#+ 	*	+&#,

7(*% &*#+ &%&		)+	#(&*#

+ 	&$(	$$,&+	"&+	#

#	"#%&%&		&%&	(	,

&"ValidateMessage())' "	)"#%&+	#	+2&&		*#

Sync+ *#,?"+(&%%				#	#2&(	%,&

"ConsumeMessage()"#%&+	*#&	#Sync+ 	

&$(	$$,&"ValidSync()"#%&%&		

:+*%*#Sync+ ,

' "	,&(	",






%+ %("#	&(	&(	) ",

ValidateMessage():

if (incoming message = Sync) then

{Message is valid,

Store it.}

ConsumeMessage():

if (stored message timer ≥ 1 tick) then

{Message is expired,

Clear it.}

ValidSync():

if (number of stored messages > 0) then

{ return true,

else

return false.}


3.4. Protocol Assumptions 

, K ,


, #		%:"&(	,

=, $		%	+#	+&	"	&	#,

, T(	#)	 %## 	(&,

>, MJJ,

@, + %#2	*##(	#%#9#2&)

2&	L-DKd/,

, &*"&*	#	2&&			(# #%(

	 )&" &(%2&			%*",-.+(+):(#&

++&+:	%(%	*	,/

3.5. The Self-Stabilizing Distributed Clock Synchronization Problem 

+(%&(	&(	)"+#&+			2&

	(	+t0)2&	t0L#	tIt0&%+(	2&&

protocol assumptions,&+:+"+#	&*"LocalTimer	(	#

+t)Net(t))#	+#%&2 ;"&"	&*	&

*"&LocalTimer	#,

rL-WK/-Kδ()/, 

LocalTimermin(x) = min (Ni.LocalTimer(x)))#

LocalTimermax(x) = max (Ni.LocalTimer(x)))	i,

Net(t)= min ((LocalTimermax(t) - LocalTimermin(t)), 

 (LocalTimermax(t - r) - LocalTimermin(t - r))),

&2 %+2	##		#	#&				3

P#&	%&	(	#)&"	+$$)###

&"((	"#&+	*2%2"*	&

LocalTimer%##PN,

C#"#&+:+"+*	 +,

Net(t))		+t)&+:+"+#	*"&LocalTimers%2

#-,,)&	*$$2/	t  t0,

π)&%&	(	)&"	#"((	"#Net(t)	t  C)

#	%"+#*	%++(	#P,

&2&(	 )&(	*&&	:C#π"&&

&2 (	(	&#,

1. Convergence: Net(C)  π) πJP

2. Closure:'	 t  C)Net(t)  π

3. Congruence:'	#Ni)	t  C)-Ni.LocalTimer(t)L/+( Net(t)  π,

4. Liveness: '	 t  C)LocalTimer*	%#;"%$

 	*"G)P - πH,B

3.6. The Self-Stabilizing Distributed Clock Synchronization Protocol For Arbitrary 

Digraphs 

&(	):"#%#)(	#' "	>#%&		#

+	2&&:"*	%$$,&if+#	 &

%&		&*(	&	#E0&	" &E4#		#";"%&

	(	,

' "	>,& $%&	(					%# 	(&=

,

&2 (	(	+	2&$	#	,

TS -LK
/-Kδ()/

P =TS)	ρL

P =-TSKδ(TS)/)	LLK#ρN

P +:--
KK/-Kδ()/)=-TSKδ(TS)//)	LLf(T)#ρN

&2 (	(	+		# 	(&),,)2&$

"#	,

TS -KK
/-Kδ()/

P  K-TSKδ(TS)/

1 	#&%($&2	$)&2 (	+"	,

CInitLP KK-Kδ()/

InitM-K/-Kδ()/

CLCInitKInit P

 MInitGuaranteedMW-Kδ()/)	t  C

πLInitGuaranteedKδ(P))MπJP)	t  C

	*"2&PL,PNTS)TSN)#&LocalTimer			& 

P-2	2	(	"#/)	*"(,



=

+E0+$:(&"+(=,-	"+(/((&

LocalTimer,

Monitor:

case (message from the corresponding node)

OSync3

ValidateMessage()

Other3

!& ,

P

ConsumeMessage()

Synchronizer:

43-LocalTimerJ/

LocalTimer3L)

43-ValidSync()#-LocalTimerJD//

LocalTimer3L)interrupted

4
3--ValidSync()#-LocalTimer  TS//

LocalTimer3L)interrupted

	+Sync)

4=3-LocalTimer  P/timed out

LocalTimer3L)

	+Sync)

43

LocalTimer3LLocalTimerK,

4. A Deductive Proof Of The Correctness Of The Protocol 

.&2(	##"*(	&		&(		&	

3	%+#(#&2	$( %2&	ρ #d ,! 

TS	+L	;"	$2# &( %&*2	$,&		)	#	

 	&:(		TS)+$#(#&( %)#&(+(%&

(	(	)2:(		+2	*")LLK)2&&+(&

TS -KK
/-Kδ()/,52*	)	((()(+ TS%:(	 	+

L	"	%&	%#	(		+,

&##"*(	(	#&	&(	(	#(	*"

-=,@/#	(	#		G
H,?#(	*#(	(		&

*	&(	2	#"#GH,?*&2*	&&(	

	#%:##*	&(	,

&(	##(#' "	@,&+&	+##	&2 ;",

"+ Sync+ # 	##P"%	 )(	

+ 	"2&&2	$2&"#% "Q.&	2	#)2E2-' "	>/

 :"##%Q.(	#	+Sync+ 2&"*	

+ "Q.&	2	#)2E3*	:"#Q)2E4*	:"#Q

Any

State Synchrony

' "	@,	((	&,

&	 &(	(	+	"#&(			#&				,

KI-KL+(###(	,/

LLK 

WLKR

MJJ

MDMJTSJP

MLocalTimerMP

. 	2#2LGD)TS/

TS -KK
/-Kδ()/

P  K-TSKδ(TS)/

?0#$+(&&P##&"((	"#&+	*2%

2"*	%%#&2	$)&")*"(#2&	(&

2#,.&	2	#)"+ &##&2#	

%&	%)2&&#	&P)&2#Pδ(P),





6E0&	" &E4' "	>		#	(	&%&		,

6++JoinTimedOut – When a node, Nj, is interrupted by an adjacent node that was timed 

out, Ni, it synchronizes with that node with a relative initial precision of ij = d + δ(D).

	RC*Nj2		"(#+t%+ Sync+ 	+Ni)%&

(	-(	E1)E2/)NjLocalTimer2&" 	&+ 		*#%)

,,)Nj,LocalTimerL,C*Ni&#+#"-(	E3&(	/)+"&*	

LocalTimer#&Sync+ 2D#+"		,

" 	#	)+t)

Ni.LocalTimerLK"++"#%K	*#	Nj,

&++"#%"##%GD)H,&")2&Ni&	&2	#	

&	#&Nj)

Dδ(D)MNi,LocalTimerMKδ(),

&	*(	"((	"#)

ijL+:--Nj,LocalTimerNi,LocalTimer//,

)

ijL-Kδ()/Lδ())#

ijL-Dδ(D)/LdKδ(D),

δ()Lδ(D)Kδ(d)#MJJ)&dIδ(d))#&		)

ijL+:-δ())dKδ(D)/

ijLdKδ(D),S

6++JoinInterrupted – When a node, Nj, is interrupted by an adjacent node that was in 

turn interrupted, Ni, it synchronizes with that node with a relative initial precision of 

ij =  + δ().

	RC*Nj2		"(#+t%+ Sync+ 	+Ni)%&

(	-(	E1)E2/)NjLocalTimer2&" 	&+ 		*

#%),,)Nj,LocalTimerL,C*Ni2		"(#-(	E1)E2&(	/)

+"&*LocalTimer#&Sync+ 2D#+"

		," 	#	)+t)

Ni.LocalTimerLK"++"#%K	*#	Nj,

&++"#%"##%GD)H,&")2&Ni&	&2	#	

&	#&Nj)

KDδ(D)MNi,LocalTimerMKKδ(),

&	*(	"((	"#)

ijL+:--Nj,LocalTimerNi,LocalTimer//,

)

ijL-
Kδ()/LKδ())#

ijL-KDδ(D)/LDδ(D),


ID)

ijL+:-Kδ())Dδ(D)/

ijLKδ(),S

?&*##&  	2#2		&(	##+	*-2#2/2&	&

# 	+ Sync+ +	&(	(&#%

	%&		 	#%&";"Sync+ ,'	+&(	-(	E1)E2/)

& 	2#2	Ni&+	*DMNi.LocalTimerJTS,

6++IgnoredNode – When a node, Nj, ignores a Sync message from an adjacent node, Ni,

the two nodes have a relative initial precision of ij < TS -D+δ(D). 

	RC*)+t)Nj 	#+ Sync+ 	+Ni)%&(	)&

DMNj.LocalTimerJTS,C*Ni&#&Sync+ 2D#+"

		)%&(	-(	E2)E3/)Ni2&			"(#	&#+#",?##	

&(	%,

RC*Ni2		"(#)+"&*LocalTimer#&Sync

+ 2D#+"		-(	E2&(	/," 	#	)

+t)

Ni.LocalTimerLK"++"#%K	*#	Nj,

&++"#%"##%GD)H,&")2&Ni&	&2	#	

&	#&Nj)

KDδ(D)MNi,LocalTimerMKKδ(),-/

&	*(	"((	"#)

ijL+:--Nj,LocalTimerNi,LocalTimer//

ijJTS-KDδ(D)/,


RC*Ni&#+#")+"&*	LocalTimer#&Sync

+ 2D#+"		-(	E3&(	/," 	#	)

+t)

Ni.LocalTimerLK"++"#%K	*#	Nj,

&++"#%"##%GD)H,&")2&Ni&	&2	#	

&	#&Nj)

Dδ(D)MNi,LocalTimerMKδ(),-
/

&	*(	"((	"#)

ijL+:--Nj,LocalTimerNi,LocalTimer//

ijJTS-Dδ(D)/,

&	*(	"((	"#)	+&*)ijJTSDKδ(D),S=

6++JoinTimedOutAfterIgnored – When all adjacent nodes are within a relative precision 

of ij < TS - D+δ(D) clock ticks of each other, for any two adjacent nodes Ni and Nj with 

Ni.LocalTimer < Nj.LocalTimer, if Nj times out, Ni will join Nj with a relative initial precision 

of ij = d + δ(D). 

	RC*+t&	*(	ij#Ni  Nj%ij)MρJJ)

D >> δ(D))ijJTS)#Pij NPTS,

P  KTSKKδ(TS))"	 TS	+&#)

PTS -K/TSKKδ(TS))#)

PijN-K/TSKKδ(TS),

+t’LtK-Pij/)2&Nj+")Ni.LocalTimer#	+#2,'	&

2	%)2"+Ni&2	#&Nj,)*&" &PijJP)

,,)δ(Pij)Jδ(P))2δ(Pij)Lδ(P)+(%& 		 "+,

Ni.LocalTimer(t’)LNi.LocalTimer(t)K-Pij/δ(Pij) 

Ni.LocalTimer(t’)LNi.LocalTimer(t)K--K/TSKKδ(TS)/δ(P)

δ(P)LKδ(TS),

Ni.LocalTimer(t’)LNi.LocalTimer(t)K-K/TS

'	+;"-/#-
/&(	6++IgnoredNode)#2#		

&2	%Ni &2	#&Nj)

Ni.LocalTimer(t)LDδ(D))#

Ni.LocalTimer(t’)IDδ(D)K-K/TS,

MρJJ)D >> δ(D))#	KI)

Ni.LocalTimer(t’)NTS,

&")2&Nj+")Ni.LocalTimer NTS#Ni(Nj0+ ,8%&6++

JoinTimedOut&2#9#Ni#Nj%&	2&&&	2&	*

(	ijLd + δ(D)$$,S

6++JoinInterruptedAfterIgnored1 – When at time t all adjacent nodes are within a 

relative precision of ij < TS - D+δ(D) clock ticks of each other, for any two adjacent nodes 

Ni and Nj with Ni.LocalTimer < Nj.LocalTimer, if Nj gets interrupted by another node at 

t’ ≥ t+TS+δ(TS), Ni will join Nj with a relative initial precision of ij =  + δ(). 

	RC*&	*(	ij#Ni  Nj%ij)+t)	&2	

%)2"+Ni&2	#&Nj,+t’LtKTSKδ(TS))

Nj.LocalTimer(t’)LNj.LocalTimer(t)KTSKδ(TS) 

Ni.LocalTimer(t’)LNj.LocalTimer(t’)δ(TS))#)

Ni.LocalTimer(t’)LNi.LocalTimer(t)KTS

'	+;"-/#-
/&(	6++IgnoredNode)#2#		

&2	%Ni &2	#&Nj)

Ni.LocalTimer(t)LDδ(D))#

Ni.LocalTimer(t’)IDδ(D)KTS,

MρJJ)D >> δ(D))&		)

Ni.LocalTimer(t’)NTS,

&")2&Nj+")Ni.LocalTimerNTS#Ni(Nj0+ ,8%&6++

JoinInterrupted&2#9#Ni#Nj%&	2&&&	2&	*

(	ijLKδ()$$,S

6++JoinInterruptedAfterIgnored2 – When all adjacent nodes are within a relative 

precision of ij < TS - D+δ(D) clock ticks of each other, for any two adjacent nodes Ni and Nj

with Ni.LocalTimer < Nj.LocalTimer, if Ni gets interrupted by another node before either Nj

times out or gets interrupted by yet another node, Nj will join Ni with a relative initial 

precision of ij = Kδ().

	RC*&	*(	ij#Ni  Nj%ij#Ni		"(#%

&	#-&	&Nj/)%&(	-(	E3/)TSMNi.LocalTimerJP),,)Ni&#

:#& 	2#2,Ni Nj)TSMNj.LocalTimerMP,8%&6++

JoinInterrupted&2#9#Ni#Nj%&	2&&&	2&	*

(	ijLKδ()$$,S


&		+&*++&	&2#+")&&	

22#ij = dKδ(D),52*	)Ni.LocalTimer < Nj.LocalTimer)Ni+"

	Nj)+(&Ni#	%	##&+"#	&%+

*	%	 Tδ(P)NTS,

.2	+&(	&+ Sync+ #&	 	#	

(##";"%	%#&	#,Sync+ #die out2&

	* # 	,"+ &+ # 	##P"%	 )

(	Sync+ 	"2&&2	$2&"*	#% "Q.&	

2	#)2E2:"##%Q.(	#	+Sync+ 

2&"*	+ "Q.&	2	#)2E3*	:"#Q52"E4Q&

2 ++##	&;",

6++NoInfiniteLoop – A Sync message always dies out.

	R8%&(	-(	E1)E2/+ #" 	#%	* 

#-DMNi.LocalTimerJTS/)&	2)	%#&	#,'	+ 

(	&	"2&&2	$	*	),,)&	#(&

2	$,8%#) L &&	 (&2	$,6#

((Sync+ 2&&%	*)	%&+ Sync+ )#

2+ 		##"+",6)+t)Ni&	#&

(&9"		"(#%&	#,)Ni.LocalTimerL#Ni2	%&

Sync+ &	##&(,+t’)&+ 2+$$Ni

		*	 &(," 	#	#"+ Ni&#)+t’)

Ni.LocalTimerLKLKL δ())

Ni.LocalTimerL-LK/KL δ(),>

8%&(	-(	E1)E2/)Ni2 	&+ DMNi.LocalTimerJTS,

+t’	Ni)

DM-LK/KL δ())LI)ID)#L δ()I)#

-LK/KL δ()JTS

-LK/KL δ()J-KK/K-KK
/δ(),

LMK)"" K	L&*;"%)2&2 ,

-KK/Kδ()KJ-KK/K-KK
/δ()

JKδ(),

 #δ() )&*;"%&#	",&")DMNi.LocalTimerJ TS

+t’#Ni2 	&+ ,&		)&+ 2#"*	&

	 "	,	")+(	+ (	2&&2	$

#%,S

6++MessageLifeSpanRA Sync message dies out in at most K( +δ()) clock ticks.

	R8%&6++NoInfiniteLoop)Sync+ 2%#",.2&

&	(&	(&)$+L(Kδ())$$	+ 	&

"	#&#",8%&#W)$+W(K δ())$$	

+ 	&&	#, )%&6++NoInfiniteLoop)&Sync

+ 2%#",LMK#WMK)	&2	%2&

&	 *"	L#W),,)K,&")$+K-+δ()/$$	Sync

+ #",S

6++IncLocalTimer – The LocalTimer of at least one node always reaches P.

	R8%&6++ NoInfiniteLoopSync+ 2%#",)%&6++

NoInfiniteLoop"2Sync+ 		#): Sync+ &

2	$2*"%#",.&Sync+ 	" 2&&

2	$)%&(	-(	E4/)&LocalTimer	+#"	&

+:+"+*"P,&		)&LocalTimer#2%	&P,S

6++NewSync – Within every time interval of P clock ticks, at least one node generates a 

new Sync message.

	R8%&6++ NoInfiniteLoopSync+ 2%#",8%&6++

MessageLifeSpanSync+ #"K-+δ()/$$,K-+δ()/JP)%

&6++IncLocalTimer#	&P,8%&(	-(	E3/)

#	&P)+"#	2Sync+ ,&		)2&*	%P

#2%+"#	2Sync + ,S

6++AllNodesTxSync – Within every time interval of P clock ticks, every node Ni

transmits at least one Sync message.

	R?(	*&++%:+ * &+,

8%&(	-(	E1/)2&Ni,LocalTimerJD)Ni#	*Sync+ )

LocalTimer	+#-(	E4/)	&D)#&#	& 	2#2,

52*	)Ni	*Sync+ )(&+ 2&"	% ,.&@

)&#LocalTimer#ID&*"	%#&

#	& 	2#2,

8%&(	2&& 	2#2-(	E1)E2/)DMNi,LocalTimerJTS)&#

	9+ Sync+ #&LocalTimer	+#-(	E4/)	&

TS)#&#:& 	2#2,

8%&(		: & 	2#2-(	E3/)TSMNi,LocalTimerMP)Ni

	*Sync+ 	+&	#)2(#	%)&	2)

LocalTimer	+#-(	E4/)	&+:+"+*"P)#&#+

")	2Sync+ )#	+&	,

&		)2&%P$$)*	%#Ni	+Sync + ,S

6++DeltaijLessThanTs – For all t  P+ clock ticks the relative initial precision of any 

two adjacent nodes Ni and Nj is ij < TS - D+δ(D).

	R8%&6++AllNodesTxSync)2&*	%+	*P$$*	%

#	+Sync+ ," 	&+ (	 #

#*	%+),,))%&6++JoinTimedOut)JoinInterrupted)#IgnoredNode)&

	*(	%2#9#Ni#Nj2&PK)dKδ(D))Kδ())

	&TSDKδ(D)$$)	(*%,&	*(	"((	

"#)&		)ijJTSDKδ(D),S

6++PrecisionLessThanWTs – For all t  P+ clock ticks the initial network precision is 

Net(t) < W(TS - D+δ(D)).

	R8%&6++DeltaijLessThanTs)	t  PK$$&	*

(	%2#9#ijJTSDKδ(D),&(	&

2	$"((	"#)%&#W)tLPK)Net(t)&"+ij),,)

Net(t)LWij,&")Net(t)JW-TSDKδ(D)/,S

6++DeltaijAboutGamma – For all t  2P+ clock ticks and upon the subsequent 

resynchronization process, the relative initial precision of any two adjacent nodes Ni and Nj

is ij =  +δ(). 

	R8%&6++PrecisionLessThanWTs)	t  PK$$&2	$

(	Net(t)JW-TSDKδ(D)/,?&&	P),,)tLPK)&Net(t)	

%&+:+"+#		&#"	P),,)δ(P),)

Net(t)JW-TSDKδ(D)/Kδ(P),

?& WMK)2WLK	&2	%)#δ(P)LKδ(TS))

Net(t)J-K/-TSDKδ(D)/KKδ(TS),

P  KTSKKδ(TS), 

PNet(t)I-KTSKKδ(TS)/--K/-TSDKδ(D)/KKδ(TS)/)#)

PNet(t)ITSK-K/-Dδ(D)/,

MρJJ)D >> δ(D)#PNet(t)NTSK-K/D,

&")tLPK)PNet(t)NTS,8%&6++ NoInfiniteLoopSync+ 2%

#",8%&6++IncLocalTimer)#"	 *	%P+	*)#

	&P#%&6++NewSync)2Sync+ 2%	#,

tI
PK#"(&";"	%&	(	)%&6++

JoinTimedOutAfterIgnored)JoinInterruptedAfterIgnored1)#JoinInterruptedAfterIgnored2

#%&	2&&	#9#2&	*(	%2

#9# dKδ(D))Kδ())#Kδ()$$)	(*%,&

(	"((	"#)&"ij = Kδ(),S

6++InitialPrecision – For all t  CInit, where CInit = 2P+K(+δ()) clock ticks, and upon 

the subsequent resynchronization process, the initial network precision is

Init = (K-1)( +δ()). 

	R8%&6++DeltaijAboutGamma)	t 
PK#"(&";"

	%&	(	)ijLKδ(),8%&#W)$+W-Kδ()/

$$	+ 	&&	#,WMK)	&2	%

2WLK,&(	&2	$"((	"#)Net(t)&

"+ij),,)Net(t)LWijL-K/-Kδ()/,&		)Net(t)L-K/-Kδ()/)#)

initL-K/-Kδ()/,S

&	+InitialConvergence – For all t  CInit, the network converges to a state where the 

guaranteed network precision is π = Init + δ(P).

	R8%&6++DeltaijAboutGamma)	t 
PK#"(&";"

	%&	(	)ijLKδ(),8%&6++InitialPrecision)	tICInit#

"(&+(&";"	%&	(	)InitL-K/-Kδ()/,

52*	)#"#	)Init2	*	+	*P%+:+"++"

δ(P),&		)	t  CInit)&"	#(	&2	$

πLInitK+:+"+#	&2	$*	P

πLInitKδ(P),

&")	t  CInit)&2	$*	 2&πL InitKδ(P)#	+2&π,S

		% InitialConvergenceTime – The initial convergence time is CInit.

	R8%&&	+InitialConvergence&2	$*	 2&CInit,S

		% InitGuaranteedPrecision – For all t  CInit and upon the completion of the 

subsequent resynchronization process, the initial guaranteed precision of the network is 

InitGuaranteedL Init.

	R8%&&	+InitialConvergence&2	$*	 2&CInit2&

(	Init,.2&"(&+(&";"

	%&	(	&"	#(	&2	$	tICInit

InitGuaranteedL Init,S

&	+InitialClosure – For all t  CInit, a synchronized network where all nodes have 

converged to π = Init + δ(P), shall remain within the synchronization precision π.

	R8%&6++InitialPrecision)	tICInit)InitL-K/-Kδ()/,8%&&	+

InitialConvergence	t  CInit&2	$&*	 #2&"	#2	$(	

πL InitKδ(P)2&" 	&+:+"+#	*	+	*P,8%&

&	+InitialConvergence#"(";"	%&	(	)&2	$

(	2	+2&π,&")&2	$&*	 #)%&	#)#

	+%&	#2&π,S

&	+InitialNetworkPrecision – For all t  CInit, where CInit = 2P+K(+δ()) clock ticks, 

the network precision is π = Init + δ(P). 

	R8%&6++InitialConvergence#&	+InitialClosure)	tICInit)

πLInitKδ(P),S

&	+InitialCongruence – For all nodes Ni and for all t  CInit, (Ni.LocalTimer(t) = )

implies Net(t) ≤ π. 

	R8%&(	-(	E3/"(+"#	LocalTimer	,8%&

6++IncLocalTimer& LocalTimer#22%	+##"

		"(#+#"#2	&,8%&(	-(	E1)E2/2&#

		"(#)	LocalTimer,&")#22%	&,8%&&	+

InitialConvergence#InitialClosure)	t  CInit)&2	$*	 #	+

%&	#2&πL InitKδ(P),&		)	t  CInit#MρJJ)2&

Ni.LocalTimer(t)L)&2	$(		+2&π),,)Net(t)Mπ)##

	%&	%,S

&(	(	#&"	#*	%	**+"	#&#+	#&

		&(	*2&&2	$(	+		#	#&	"#	%

-++"+#+:+"+/*",52*	)"(&*	 #"	)&		

"+	2%&* &	(	,"&+&#	#"#G@8H)

2&	)2((	)&	(	*		protocol that is based on the initial 

synchrony assumptions is "#&*&optimum precision of the coarsely 

synchronized system,&	+&#%## 2	#+$		2	 $2&

	(	%(	*#&	"2#	 +	(&G?BBHGC#


HG8	

HG5

)
HG6
HGC+
H,&#)#"#G


H)	(	+	%"#&**	 )""#&* &	

(	,&	%&	+&#)(	#2)&+(%	;"	+	+,

		+&+&##(#(	+	%&#		,

'	+&:(		InitL(K-1)( +δ())*#&&%&	+)C)#

(	) π)	"&	(&( %#&#		)(%)&	(&0

2#&#&+"#	&2	$:(	,.&	2	#)

CLf (T, ρ)Lf (W, δ(P)))#

πLf (T, ρ)Lf (W, δ(P)),B


&&	;"	Init+(&##+#	,.

(	"	)	&#	)2&	ρ L#dL)#	&+#	)2&	

ρ L#d ) InitL-K/,

&"	#&(	(	)2"+#MρJJ,&(	)&2*	)&&

"#		#),,)MρJ,?&ρ NN"&&δ()  )%&&	+

InitialConvergence)	t  CInit#"(";"	%&	(	)&

2	$*	 2&πL InitKδ(P),.&	2	#)#"&& &	#	)"	&	

+(	*+Init#&2	$(	)π)"	#,&")2&ρ NN)

InitGuaranteedMInit)#"	&	+(	*+Init&*#T&		)+(	*+

π"	#,'"	&	+	)&*	 +C"##%CInit),,)CLCInit,

52*	)ρJJ)&" &&-	/%&	%)Init)"	2&CInit)&

 "	#%&	%)InitGuaranteed)$(	"+	(	##"(&* &

%&	%),,)Init,?#+	&%&2 ++	&+#

	2&	ρL)dI)#LDKd,

6++ρdJoinTimedOut – For ρ = 0, when a node, Nj, is interrupted by an adjacent node 

that was timed out, Ni, it synchronizes with that node with a relative initial precision 

of ij = d.

	R8%&6++JoinTimedOut) ij = dKδ(D),ρL#dI)ijLd,S

6++ρdJoinInterrupted – For ρ = 0, when a node, Nj, is interrupted by an adjacent node 

that was in turn interrupted, Ni, it synchronizes with that node with a relative initial precision 

of ij = .

	R8%&6++JoinInterrupted) ij =Kδ(),ρL#dI)ijL,S

6++ρdDeltaijAboutGamma – For ρ = 0, for all t  2P+ clock ticks, the relative initial 

precision of any two adjacent nodes Ni and Nj is ij = .

	R8%&6++DeltaijAboutGamma)ij = Kδ(),ρL#dI)ijL,S

6++ρdInitialPrecision – For ρ = 0, for all t  CInit, where CInit = 2P+K clock ticks, and 

upon the subsequent resynchronization process, the initial network precision is Init = (K-1). 

	R8%&6++InitialPrecision)	tICInit) InitL-K/-Kδ()/,ρL

#dI)InitL-K/,S

6++ρdInitGuaranteedPrecision – For ρ = 0 and for all t  C, the initial guaranteed 

precision is InitGuaranteed = Wd. 

	R8%&&	+InitialConvergence#InitialClosure)&2	$&*	 #)

%&	#)#	+%&	#	tICInit#"(";"

	%&	(	)&2	$*	 Net(t)L InitKδ(P),ρL)

Net(t)L Init,8%&6++ρdDeltaijAboutGamma	t  CInit)#9#	

2&ijL&&	,52*	)ρL#dI)	t  CInit#"(

";"	%&	(	)%&6++ρdJoinTimedOut2

#9#2%&	2&ijLd,&")#(		%&	

(	),,)(	 P)2%&	2	#2&ijLd,1( &

(		InitLW(	#)2	"%&	#2	$2&(	

ijLd	%2#9#Ni#Nj#"	#(	

InitGuaranteedLWd	&	2	$,S

		% ρdPrecision – For ρ = 0, the precision of the network is π = Wd.

	R8%&6++ρdInitGuaranteedPrecision)	ρL)&2	$*	 

InitGuaranteedLWd,1&πLInitGuaranteedKδ(P),ρL#dI)πLWd,S

		% ρdConvergenceTime – For ρ = 0, the convergence time is C = CInit + Init / P.

	R8%&6++ρdInitGuaranteedPrecision)	ρL)&2	$*	 

InitGuaranteedLWd2&CLCInitKInit P,S


&2&dL),,)	&#	)LD)InitGuaranteedL)#πL,?2

&	++#&	+&+(	),,)	MρJJ#dI

#	t  C,

&	+Convergence – For all t  C, the network converges to a state where the 

guaranteed network precision is π, i.e., Net(t) ≤ π.

	R8%#)	tIC)πLInitGuaranteedKδ(P),8%&&	+

InitialConvergence)	tICInit)πLInitKδ(P),'	MρJJ)2&"(

&+(";"	%&	(	),,)	tIC2&	CICInit)

&"	#(	&2	$Init#"(";"	%&	

(	)"	&	+(	*+Init"	#,&		)+(	*+

InitGuaranteed&*#,)%&		% InitGuaranteedPrecision)

InitGuaranteedLInit#+(	*+π"	#,)&

+:+"+#		+	*P"##%δ(P))&2	$&*	 #2&

(	π#	+2&π,S

&	+Closure – For all t  C, a synchronized network where all nodes have converged to 

Net(t) ≤ π, shall remain within the synchronization precision π.

	R8%&&	+Convergence)	tIC)&2	$*	 2&&(	

πLInitGuaranteed Kδ(P),.2&	MρJJ#	tIC)"(";"

	%&	(	&2	$(		+2&π,&		)&2	$

&*	 #)%&	#)#	+%&	#2&π,S

&	+Congruence – For all nodes Ni and for all t  C, (Ni.LocalTimer(t) = ) implies 

Net(t) ≤ π.

	R8%&(	-(	E3/"(+"#	LocalTimer	,8%&

6++IncLocalTimer& LocalTimer#22%	+##)"

		"(#)+#"#2	&,8%&(	-(	E1)E2/2&#

		"(#)	LocalTimer,&")#22%	&,8%&&	+

Convergence#Closure)	t  C)&2	$*	 #	+%&	#

2&πL InitGuaranteedKδ(P),&")	t  C#MρJJ)2&Ni.LocalTimer(t)L)

&2	$(		+2&π),,)Net(t)Mπ)##	%&	%,S

6++InitGuaranteedPrecision – For all t  C, the initial guaranteed precision of the 

network is Wd ≤ InitGuaranteed ≤ (K-1)(+δ()), where InitGuaranteed = Wd, for ρ = 0, and 

InitGuaranteed ≤ (K - 1)(+δ()), for ρ > 0. 

	R8%&6++InitialPrecision)	MρJJ#	tICInit#"(

&";"	%&	(	)&2	$(	

InitL-K/- +δ()/,8%&&	+InitialConvergence)	MρJJ#tICInit#

"(&+(&";"	%&	(	)&"	#

(	&2	$Init)&	2	#)InitGuaranteedLInit,8%&6++

ρdInitGuaranteedPrecision)	ρL#	t  C)&"	#(	

InitGuaranteedLWd,&")	MρJJ#	t  C)&"	#(	

"##%WdMInitGuaranteedM-K/(+δ()),S

&	+GuaranteedPrecision – For for all t  C, the guaranteed precision of the network is 

bounded by Wd ≤ π ≤ InitGuaranteed + δ(P). 

	R8%&6++InitGuaranteedPrecision)	tIC#MρJJ)&

2	$(	"##%WdMInitGuaranteedM-K/(+δ())2&&2	"#

	ρL#&"((	"#	ρN,8%#)	tIC)πLInitGuaranteedKδ(P),

&		)	MρJJ#	tIC)&"	#(	&2	$

"##%WdMπMInitGuaranteedKδ(P),S


&2&dL),,)	&#	)LD)InitGuaranteedL)#πL,

6++ ConvergenceTime – The convergence time is C = CInit + Init P. 

	R8%&&	+InitialConvergence)	MρJJ)&2	$*	 2&

CInit,8%&		% ρdConvergenceTime)	ρL)&*	 + CLCInitK

Init P,&*	 +"((	"#)	MρJJ)&*	 

+CLCInitKInit P,S

&	+Liveness – For all t  C, LocalTimer of every node sequentially takes on at least all 

integer values in [, P - π].

	R8%&&	+Convergence#Closure)	t  C)%&	#2	$

2&	#&**	 #π)	+2&π,&2	$%&	#)

#&	+"			"(#%+#"#9#2&π,'	&

2	%)2&&#	&P)+"#	+2Sync

+ )&2#Pπ,.&2##9&#)

 		"(#2&&:,.&2#	&2%	+&#)

+"2&π,.&2#		"(#		& P)%&(	

-(	E1)E2/)LocalTimer2&" 	&+ 		*#%),,)

LocalTimerL,'	&2	%&*(	(	%)&2#

#9&#,&2	$%&	%)&2#2

		"(# "#+"2&&:P,&		)&2#

;"%$ 	*"G)PπH,&#)&2*	);"%

$ 	*"G)PH,'"	&	+	)"(*	 &(		(

#"	 *	%P+	*#	*	%	%&	(	,&")	t  C)

#;"%$ 	*"G)PπH,S


5. Conclusions 

.&	(	)2(	###"*(	&		 #	"#

$%&	(	&"#&#	"#%&				%)

"	)#(	## 	(&	  	+"%##2	$

#2&2 	#	&2	$+,?(	###"*(	

&		&(	((&2	$2&"#	#

#	$,?	+#&+#	++#	*	 ,&

(	#	%"+("&&%+#	$	

	%	# )(")	+ "#,
#	%+"),,)&%#

&*";"#,&	&	+&+:+"+"+	(	( 

#,&%	&&*	&#&&	2&&	#

			###$#	,

?&*&2#(	*&2%&				%# 	(&&",

&		" &"(&2 ;",			%# 	(&%&	#&

(	"Q?&%("			%# 	(&	Q6$ &

(	+	+#	(	(*)&"	%++	)2&%(	(&

%&	&	(	Q?&&"	%++	-8%/)2&%(

 	(&%&	&	(	Q=

References 

G8	
H8	&),T	)6,,3U%&	+?	#%+)V&%,

1*,6,B-

/>)
,

G8"H8"	)1,3U(	+		&"	*"	)V




>)'	"	%,

GC#HC#),,T5"),D,3U%&	"&"(#+(2&+

2	#	)V&%,1*,4@
-
/@BR@=),

GC	>HC	"),T1")4,3U# '"	!	"#%+	!	

		%&)V4	
&	+("	)*,

==)((,)>,

GC+HC+C	#)W,T	)E,T	),3U&%&	

+(:
2	$)V&%,1*,6,B-
/)=),

G5
H5 )5,T&),E,TD+)8,W,3U%&	+2	#2	$)V

&%,1*,4@>-

/
@=B)
,

G5H5 )5,TD+)8,W,T&),E,T	$)5,3U'	&(	#	

%&	%+(:2	$)V&%,1*,4@B-
/@>),

GD(BBHD()53U1+%+)! 	(	!	"#4+###

(()VD"2	#+"&	).8
B
=BB)BB,

G6H6),T&)C,3U&%&	+2	#2	$&

	)V&%=-
/=RB),

G@H$("	),1,38%'"	 		

!	"#$%&	%+,4 &&.	%+("+

)%)#"	%!	"#%+-@/)
*+	


@,

G@8H$("	),1,3U8%'"	 		

!	"#$%&	%+,V

@
=

)((,=)

" "@,

GH$("	),1,3U !	"#$%&		

'				%! 	(&V,


>)((,
)'	"	%,

G8H$("	),1,3U#&$  !	"#$

%&		'				%! 	(&V,


>
)((,

=)%,

G	>H		+)?T$("	),1,T	),,3187
3"	

	#++"%+,

>
=>)((,
)	&


>,

G?BBH?)!,W,T	 ),5,3U*#%+0+2	#02	$)V


"	-6#/=B=))BB,

Appendix A. Symbols 

&%+"#&(		#	##G$("	H#	#&	

			,

Symbols Descriptions 

K"+#

T2	$( %

D*	(#%

d2	$+(	

"###		2&	(	+

P%&	(	#

F"+"%#



Ni&&#

Mi&&+	#

++"%

L&	 (&	(&

W&2#&	#+	&	(&

TS	(&&	&#

π&"	#%&	(	

C*	 +

CInit+%&	%

LocalTimer#0 $

ij(	2LocalTimers%2#9#Ni#Nj

Init(	+ LocalTimers#++#%	

	%&	(	

InitGuaranteed"	#(	+ LocalTimers#++#%	

	%&	(	

δ(t)#	(	t 

Sync%&	+ 

Net(t)(	+ LocalTimers#+t 
REPORT DOCUMENTATION PAGE Form Approved

OMB No. 0704-0188

2. REPORT TYPE 

Technical Memorandum

 4. TITLE AND SUBTITLE

Correctness Proof of a Self-Stabilizing Distributed Clock Synchronization 

Protocol for Arbitrary Digraphs

5a. CONTRACT NUMBER

 6. AUTHOR(S)

Malekpour, Mahyar R.

 7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES)

NASA Langley Research Center

Hampton, VA 23681-2199

 9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES)

National Aeronautics and Space Administration

Washington, DC 20546-0001

 8. PERFORMING ORGANIZATION

 REPORT NUMBER

L-20066

10. SPONSOR/MONITOR'S ACRONYM(S)

NASA

13. SUPPLEMENTARY NOTES

12. DISTRIBUTION/AVAILABILITY STATEMENT

Unclassified Unlimited

Subject Category 62 

Availability: NASA CASI (443) 757-5802

19a. NAME OF RESPONSIBLE PERSON

STI Help Desk (email: help@sti.nasa.gov)

14. ABSTRACT

This report presents a deductive proof of a self-stabilizing distributed clock synchronization protocol. It is focused on the 

distributed clock synchronization of an arbitrary, non-partitioned digraph ranging from fully connected to 1-connected 

networks of nodes while allowing for differences in the network elements. This protocol does not rely on assumptions about 

the initial state of the system, and no central clock or a centrally generated signal, pulse, or message is used. Nodes are 

anonymous, i.e., they do not have unique identities. There is no theoretical limit on the maximum number of participating 

nodes. The only constraint on the behavior of the node is that the interactions with other nodes are restricted to defined links

and interfaces. We present a deductive proof of the correctness of the protocol as it applies to the networks with unidirectional

and bidirectional links. We also confirm the claims of determinism and linear convergence. 

15. SUBJECT TERMS

Algorithm; Clock synchronization; Communication network; Digraph; Distributed; Emergent system; Protocol; 

Self-stabilizing

18. NUMBER

 OF 

 PAGES

31

19b. TELEPHONE NUMBER (Include area code)

(443) 757-5802

a. REPORT

U

c. THIS PAGE

U

b. ABSTRACT

U

17. LIMITATION OF 

 ABSTRACT

UU

Prescribed by ANSI Std. Z39.18

Standard Form 298 (Rev. 8-98)

3. DATES COVERED (From - To)

5b. GRANT NUMBER

5c. PROGRAM ELEMENT NUMBER

5d. PROJECT NUMBER

5e. TASK NUMBER

5f. WORK UNIT NUMBER

534723.02.02.07.30

11. SPONSOR/MONITOR'S REPORT

 NUMBER(S)

NASA/TM-2011-217184

16. SECURITY CLASSIFICATION OF:

The public reporting burden for this collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, 

gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this 

collection of information, including suggestions for reducing this burden, to Department of Defense, Washington Headquarters Services, Directorate for Information Operations and 

Reports (0704-0188), 1215 Jefferson Davis Highway, Suite 1204, Arlington, VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person 

shall be subject to any penalty for failing to comply with a collection of information if it does not display a currently valid OMB control number. PLEASE DO NOT RETURN YOUR FORM TO THE ABOVE ADDRESS.

1. REPORT DATE (DD-MM-YYYY)

01- 10 - 2011