dc.contributor.authorZhang, Lu
dc.contributor.authorTang, Xueyan
dc.contributor.authorHe, Bingsheng
dc.date.accessioned2017-09-28T06:48:11Z
dc.date.available2017-09-28T06:48:11Z
dc.date.issued2016
dc.identifier.citationZhang, L., Tang, X., & He, B. Analysis of Minimum Interaction Time for Continuous Distributed Interactive Computing. IEEE Transactions on Parallel and Distributed Systems, 28(2), 401-415.en_US
dc.identifier.issn1045-9219en_US
dc.identifier.urihttp://hdl.handle.net/10220/43813
dc.description.abstractDistributed interactive computing allows participants at different locations to interact with each other in real time. In this paper, we study the interaction times of continuous Distributed Interactive Applications (DIAs) in which the application states change due to not only user-initiated operations but also time passing. Given the clients and servers of a continuous DIA, its interaction time is directly affected by how the clients are assigned to the servers as well as the simulation time settings of the servers. We formulate the Minimum Interaction Time (MIT) problem as a combinatorial problem of these two tuning knobs and prove that it is NP-hard. We then approximate the problem by fixing the client assignment or the simulation time offsets among the servers. When the client assignment is fixed, we show that finding the minimum achievable interaction time can be reduced to a weighted bipartite matching problem. We further show that this approach establishes a tight approximation factor of 3 to the MIT problem if each client is assigned to its nearest server. When the simulation time offsets among the servers are fixed, we show that finding the minimum achievable interaction time is still NP-hard. This approach can approximate the MIT problem by a factor within 2 if the simulation times of all servers are synchronized. A mix of the above two approaches better approximates the MIT problem within a factor of 5/3. We further conduct experimental evaluation of these approaches with three real Internet latency datasets.en_US
dc.description.sponsorshipMOE (Min. of Education, S’pore)en_US
dc.language.isoenen_US
dc.relation.ispartofseriesIEEE Transactions on Parallel and Distributed Systemsen_US
dc.rights© 2016 IEEE.en_US
dc.subjectDistributed Interactive Computingen_US
dc.subjectInteraction Timeen_US
dc.titleAnalysis of Minimum Interaction Time for Continuous Distributed Interactive Computingen_US
dc.typeJournal Article
dc.contributor.schoolSchool of Computer Science and Engineeringen_US
dc.identifier.doihttp://dx.doi.org/10.1109/TPDS.2016.2585140


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record