World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Distributed Queuing in Dynamic Networks

    We consider the problem of forming a distributed queue in the synchronous dynamic network model of Kuhn, Lynch, and Oshman (STOC 2010) in which the network topology changes from round to round but the network stays connected. Queue requests may arrive over rounds at network nodes and the goal is to eventually enqueue them in a distributed queue. We show that in 1-interval connected graphs, where the communication links change arbitrarily between every round, it is possible to solve the distributed queueing problem in O(nk) rounds using O(logn) size messages, where n is the number of nodes in the network and kn is the number of queue requests. Further, we show that for more stable graphs, e.g. T-interval connected graphs where the communication links change in every T2 rounds, the distributed queuing problem can be solved in O(n+nkmin{α,T}) rounds using the same O(logn) size messages, where α>0 is the concurrency level parameter that captures the minimum number of active queue requests in the system at any round. These results hold in any arbitrary arrival of queue requests and ensure correctness of the queue formed. To our best knowledge, these are the first solutions to the distributed queuing problem in highly dynamic networks.

    A preliminary version of this paper appeared in FOMC 2013 [18].

    Communicated by P. Spirakis