標題: On detection of bounded global predicates
作者: Wu, IC
Chen, LB
資訊工程學系
Department of Computer Science
公開日期: 1-Jan-1998
摘要: Distributed programs often follow some bounded global predicates, for example, the total number of certain tokens is always the same or bounded in a range. In order to detect bounded global predicates, we can first derive the minimum and maximum global snapshots and then check if the minimum and maximum are out of the range, Recently, Chase and Garg proposed an efficient method to derive the minimum global snapshot by reducing this problem to a maximum network flow problem. A restriction of this method is that all message values (e.g,, the token number in messages) must be zero and all process state values (e.g,, the token number in processes) must be non-negative. In this paper, we propose an elegant technique, called normalization. By using this technique, we can remove the above restriction and also derive the minimum and maximum global snapshots at the same time.
URI: http://dx.doi.org/10.1093/comjnl/41.4.231
http://hdl.handle.net/11536/150393
ISSN: 0010-4620
DOI: 10.1093/comjnl/41.4.231
期刊: COMPUTER JOURNAL
Volume: 41
起始頁: 231
結束頁: 237
Appears in Collections:Articles