Coda File System

Re: Coda Version Vectors

From: Jan Harkes <>
Date: Thu, 22 Jul 2004 23:03:38 -0400
On Mon, Jul 19, 2004 at 03:08:24PM +0800, Sandeep Kumar wrote:
> The maintenance of version vectors for detecting write/write conflicts 
> in Coda as described in Tanenbaum and Van Steen's *Distributed Systems* 
> book (p. 617) seems to be different than the scheme alluded to by Jim 
> Kistler in his Ph.D. thesis (p. 45) which seems to be that of LOCUS 
> (Scott Parker et al 1983). Yet, it seems (I may be totally incorrect) 
> that both schemes detect conflicts correctly because the DAG induced by 
> the partition graph works with both schemes (given the usual notion of 
> vector dominance). If that's true, which one does Coda use and why does 
> it prefer one over the other?

Kistler describes the same algorithm as Tanenbaum and van Steen. I think
your problem stems from the fact that you are assuming some sort of
background (passive?) replication that happens after an update is
committed at one location.

> Here, I've (arbitrarily) considered the update in the A&B partition to 
> be initiated by A. It could've been considered as an update by B.

However, Coda uses a strategy where it sends updates to all replicas
simultaneously. Ofcourse at this point we don't know whether the
operation will actually succeed everywhere, so once we collected the
responses we follow up with a COP2 message (concurrent operation phase 2?)
which synchronizes the version vectors.

initial		operation	COP2
A [1,1,1]	[2,1,1]		[2,2,2]
B [1,1,1]	[1,2,1]		[2,2,2]
C [1,1,1]	[1,1,2]		[2,2,2]

Now if server C was unreachable we get the following

initial		operation	COP2
A [1,1,1]	[2,1,1]		[2,2,1]
B [1,1,1]	[1,2,1]		[2,2,1]
C [1,1,1]			[1,1,1]

Received on 2004-07-22 23:06:34