https://scholars.lib.ntu.edu.tw/handle/123456789/457567
標題: | Strong interaction fairness via randomization | 作者: | YUH-JZER JOUNG Smolka, S.A. |
關鍵字: | Committee coordination; Distributed algorithms; Multiparty interaction; Randomized algorithms; Strong interaction fairness; Weak interaction fairness | 公開日期: | 1998 | 卷: | 9 | 期: | 2 | 起(迄)頁: | 137-149 | 來源出版物: | IEEE Transactions on Parallel and Distributed Systems | 摘要: | We present MULTI, a symmetric, distributed, randomized algorithm that, with probability one, schedules multiparty interactions in a strongly fair manner. To our knowledge, MULTI is the first algorithm for strong interaction fairness to appear in the literature. Moreover, the expected time taken by MULTI to establish an interaction is a constant not depending on the total number of processes in the system. In this sense, MULTI guarantees real-time response. MULTI makes no assumptions (other than boundedness) about the time it takes processes to communicate. It, thus, offers an appealing tonic to the impossibility results of Tsay and Bagrodia, and Joung concerning strong interaction fairness in an environment, shared-memory, or message-passing, in which processes are deterministic and the communication time is nonnegligible. Because strong interaction fairness is as strong a fairness condition that one might actually want to impose in practice, our results indicate that randomization may also prove fruitful for other notions of fairness lacking deterministic realizations and requiring real-time response. © 1998 IEEE. |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/457567 | ISSN: | 10459219 | DOI: | 10.1109/71.663873 | SDG/關鍵字: | Data communication systems; Data storage equipment; Distributed computer systems; Random processes; Real time systems; Response time (computer systems); Distributed algorithms; Multiparty interaction; Randomized algorithms; Algorithms |
顯示於: | 資訊管理學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。