Chinese Journal of Computers   Full Text
Title	A Plausible Timestamp System in Hierarchical Architecture
Authors	CHEN Chun-Peng1),2) WANG Huai-Min1) YAO Yi-Ping1)
Address	1)(School of Computer Science, National University of Defense Technology, Changsha 410073) 2)(No.91404 Troop, Qinhuangdao, Hebei 066001)
Year	2008
Issue	No.3(456—466)
Abstract &   Background	Abstract Currently, in distributed systems there are more and more processes which are hierarchically distributed in the wide area network, which make it hard to realize the causality in the distributed systems. In a distributed system with N sites, the precise detection of causal relationships between events can only be done with vector clocks of size N. This gives rise to scalability and efficiency problems for vector clocks. In this paper, a kind of hierarchical architecture is described in which proxy process is used to exchange messages between the subgroups and global group can be composed to achieve some objectives. A plausible timestamp system is presented using divide-and-conquer approach, in which only a part of the timestamp is attached to the message as the tag whenever the message is transmitted. The timestamp system allows to detecting causality between events in a large distributed system with high degree of accuracy, enhancing the scalability of the system and minimizing the affection because of adding or reducing federates. keywords plausible clock; hierarchical architecture; proxy process; divide-and-conquer; simulation background Currently, networks over which distributed systems running possess multilevel hierarchical structure, where certain sets of physical or logical nodes are grouped together according to physical, geographical, and/or administrative consideration. A hierarchical network is a traditional solution to the scaling problem. In the literature ［Taguchi et al. 2003］, a hierarchical group of processes are discussed to support hundreds of processes. In the literature ［Kawanami et al. 2004］, processes in local subgroups use physical and linear clocks while processes in a wide-area network adopt vector clock. However, this method is applicable in the specific case, and it can not resolve the expansibility because there are two levels in the hierarchical group. A new time stamping system is proposed, called Hierarchical Vector Clock, which allows to detect causality between events in a large distributed system, while being ideally suited for the hierarchical structure of an underlying network and able to scale gracefully with the increasing number of distributed sites ［Khotimsky and Zhuklinets 1999］. However, in this time stamping system, each process should maintain a much longer timestamp which includes vector in the lowest peer group and vectors in the all higher peer group until in the peer group of the highest level and the whole timestamp should be attached to the messages even if the messages be transmitted in the local peer group. So, the communication overhead can be much larger with the advance of the level distance because a given process tends to interact frequently with only the processes in the same peer group.In this paper, the authors present a plausible time stamping system in the hierarchical architecture. At the same time, in the current HLA application, Hierarchical Federation Community (HFC) and Time Management (TM) mechanism in the architecture was researched. However, it has not been proved to be correct, although the implementation of the TM services within the HFC architecture was discussed in the literature［Cramp et al. 2002］. And, the HLA TM services are not available to Hierarchical Architecture ［Snively et al. 2004］. At first the protocol used in the HLA TM service is the main objective, but now it is extended to the distributed system.