Atul Adya, Barbara Liskov
Laboratory for Computer Science,
Massachusetts Institute of Technology,
545 Technology Square, Cambridge, MA 02139
{adya,liskov}@lcs.mit.edu
A Postcript version of this paper is also available.
The scheme uses multipart timestamps to inform nodes about information they need to know. Today the utility of such schemes is limited because timestamp size is proportional to system size and therefore the schemes don't scale to very large systems. We show how to solve this problem. Our multipart timestamps are based on real rather than logical clocks; we assume clocks in the system are loosely synchronized. Clocks allow us to keep multipart timestamps small with minimal impact on performance: we remove old information that is likely to be known while retaining recent information. Only performance and not correctness is affected if clocks get out of synch.
This paper appears in the Proceedings of the ACM Symposium on Principles
of Distributed Computing (PODC '97), Santa Barbara, CA, August 1997.
This research was supported in part by the Advanced Research Projects
Agency of the Department of Defense, monitored by the Office of Naval
Research under contract N00014-91-J-4136.
Copyright 
1997 by the Association for Computing Machinery, Inc.
Permission to make digital or hard copies of part or all of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. Copyrights for
components of this work owned by others than ACM must be honored.
Abstracting with credit is permitted. To copy otherwise, to republish, to
post on servers, or to redistribute to lists, requires prior specific
permission and/or a fee. Request permissions from Publications Dept, ACM
Inc., fax +1 (212) 869-0481, or permissions@acm.org
This research was supported in part by the Advanced Research Projects
Agency of the Department of Defense, monitored by the Office of Naval
Research under contract N00014-91-J-4136.
Copyright 1997 by the Association for Computing Machinery, Inc.
Permission to make digital or hard copies of part or all of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. Copyrights for
components of this work owned by others than ACM must be honored.
Abstracting with credit is permitted. To copy otherwise, to republish, to
post on servers, or to redistribute to lists, requires prior specific
permission and/or a fee. Request permissions from Publications Dept, ACM
Inc., fax +1 (212) 869-0481, or permissions@acm.org