Article

Free access

Pushing dependent data in clients-providers-servers systems

Authors:

Amotz Bar-Noy,

Joseph (Seffi) Naor,

Baruch SchieberAuthors Info & Claims

MobiCom '00: Proceedings of the 6th annual international conference on Mobile computing and networking

Pages 222 - 230

https://doi.org/10.1145/345910.345950

Published: 01 August 2000 Publication History

PDF eReader

Abstract

In a satellite and wireless networks and in advanced traffic information systems in which the up-link bandwidth is very limited, a server broadcasts data files in a round-robin manner. The data files are provided by different providers and are accessed by many clients. The providers are independent and therefore files may share information. The clients who access these files may have different patterns of access. Some clients may wish to access more than one file at a time in any order, some clients may access one file out of of several files, and some clients may wish to access a second file only after accessing another file. The goal of the server is to order the files in a way that minimizes the access time of the clients given some a-priori knowledge of their access patterns. This paper introduces a clients-providers-servers model that represents certain environments better than the traditional clients-servers model. Then, we show that a random order of the data files performs well independent of the specific access pattern. Our main technical contribution is showing how to de-randomize the randomized algorithm that is based on selecting a random order. The resulting algorithm is a polynomial time deterministic algorithm that finds an order that achieves the bounds of the random order.

References

[1]

S. Acharya, R. Alonso, M. J. Franklin, and S. Zdonik. Broadcast Disks: data management for asymmetric communications Environment. Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 95), San jose, CA, 199-210, 1995.

Digital Library

Google Scholar

[2]

S. Acharya, M. J. Franklin, and S. Zdonik. Dissemination-based Data Delivery Using Broadcast Disks. IEEE Personal Communications, Vol. 2(6), 50-60, 1995.

Google Scholar

[3]

N. Alon and J. Spencer. The Probabilistic Method. John Wiley and Sons Inc., 1992.

Google Scholar

[4]

M. H. Ammar and J. W. Wong. The Design of Teletext broadcast cycles. Performance Evaluation, Vol. 5(4), 235-242, 1985.

Crossref

Google Scholar

[5]

M. H. Ammax and J. W. Wong. On the optimality of cyclic transmission in Teletext systems. IEEE Transaction on Communication, COM-35(1), 68-73, 1987.

Google Scholar

[6]

A. Bar-Noy, R. Bhatia, J. Naor, and B. Schieber. Minimizing Service and Operation Costs of Periodic Scheduling. Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 98), 11-20, 1998.

Digital Library

Google Scholar

[7]

T. Imielinski, S. Viswanathan, and B. Badrinath. Energy efficient indexing on air. Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 94) 25-36, 1994.

Digital Library

Google Scholar

[8]

C. Kenyon and N. Schabanel. The data broadcast problem with non-uniform transmission times. Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 99), 547-556, 1999.

Digital Library

Google Scholar

[9]

M. Naor and O. Reingold. Private communication.

Google Scholar

[10]

S. Rao and A. Richa. New approximation techniques for some ordering problems. Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 98), 211-218, 1998.

Digital Library

Google Scholar

[11]

C. J. Su and L. Tassiulas. Broadcast Scheduling for Information Distribution. Proceedings of the 16th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 97), 109-117, 1997.

Digital Library

Google Scholar

[12]

N. Vaidya and S. Hameed. Log time algorithms for scheduling single and multiple channel data broadcast. Proceedings of the 3rd Annual ACM/IEEE International Conference on Mobile Computing and Networking, 90-99, 1997.

Digital Library

Google Scholar

Cited By

View all

Liaskos CPetridou SPapadimitriou G(2011)Towards realizable, low-cost broadcast systems for dynamic environmentsIEEE/ACM Transactions on Networking10.1109/TNET.2010.206253419:2(383-392)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1109/TNET.2010.2062534
Waluyo ARahayu WTaniar DScrinivasan B(2011)A Novel Structure and Access Mechanism for Mobile Data Broadcast in Digital EcosystemsIEEE Transactions on Industrial Electronics10.1109/TIE.2009.203545758:6(2173-2182)Online publication date: Jun-2011
https://doi.org/10.1109/TIE.2009.2035457
Liaskos CPetridou SPapadimitriou G(2010)Cost-Aware Wireless Data BroadcastingIEEE Transactions on Broadcasting10.1109/TBC.2009.203952156:1(66-76)Online publication date: Mar-2010
https://doi.org/10.1109/TBC.2009.2039521
Show More Cited By

Index Terms

Pushing dependent data in clients-providers-servers systems

Recommendations

Pushing dependent data in clients-providers-servers systems

In satellite and wireless networks and in advanced traffic information systems in which the up-link bandwidth is very limited, a server broadcasts data files in a round-robin manner. The data files are provided by different providers and are accessed by ...
A Parallel Hill Climbing Algorithm for Pushing Dependent Data in Clients-Providers-Servers Systems
ISCC '02: Proceedings of the Seventh International Symposium on Computers and Communications (ISCC'02)

The up-link bandwidth in satellite networks and in advanced traffic wireless information system is very limited. A server broadcasts data files provided by different independent providers and accessed by many clients in a round-robin manner. The clients ...
A parallel hill climbing algorithm for pushing dependent data in clients-providers-servers systems

The up-link bandwidth in satellite networks and in advanced traffic wireless information system is very limited. A server broadcasts data files provided by different independent providers and accessed by many clients in a round-robin manner. The clients ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

MobiCom '00: Proceedings of the 6th annual international conference on Mobile computing and networking

August 2000

300 pages

ISBN:1581131976

DOI:10.1145/345910

Chairmen:
Raymond Pickholtz
George Washington Univ., Washington, DC
,
Sajal K. Das
Univ. of Texas at Arlington, Arlington
,
Ramon Caceres
AT&T Labs
,
J. J. Garcia-Luna-Aceves
Univ. of California, Santa Cruz, Santa Cruz

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

MobiCom00

Sponsor:

SIGMETRICS
SIGCOMM
SIGMOBILE
IEICE
IFIP WG 6.3

MobiCom00: The 6th Annual International Conference on Mobile Computing and Networking

August 6 - 11, 2000

Massachusetts, Boston, USA

Acceptance Rates

MobiCom '00 Paper Acceptance Rate 28 of 226 submissions, 12%;

Overall Acceptance Rate 440 of 2,972 submissions, 15%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
344
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)5

Reflects downloads up to 28 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liaskos CPetridou SPapadimitriou G(2011)Towards realizable, low-cost broadcast systems for dynamic environmentsIEEE/ACM Transactions on Networking10.1109/TNET.2010.206253419:2(383-392)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1109/TNET.2010.2062534
Waluyo ARahayu WTaniar DScrinivasan B(2011)A Novel Structure and Access Mechanism for Mobile Data Broadcast in Digital EcosystemsIEEE Transactions on Industrial Electronics10.1109/TIE.2009.203545758:6(2173-2182)Online publication date: Jun-2011
https://doi.org/10.1109/TIE.2009.2035457
Liaskos CPetridou SPapadimitriou G(2010)Cost-Aware Wireless Data BroadcastingIEEE Transactions on Broadcasting10.1109/TBC.2009.203952156:1(66-76)Online publication date: Mar-2010
https://doi.org/10.1109/TBC.2009.2039521
Huang JHuang J(2010)Exploiting replication on dependent data allocation for ordered queries over multiple broadcast channelsWireless Networks10.1007/s11276-009-0230-x16:7(1817-1836)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1007/s11276-009-0230-x
Waluyo ASrinivasan BTaniar D(2009)Data Dissemination in Mobile DatabasesEncyclopedia of Information Science and Technology, Second Edition10.4018/978-1-60566-026-4.ch146(914-920)Online publication date: 2009
https://doi.org/10.4018/978-1-60566-026-4.ch146
Hu CChen M(2009)Online Scheduling Sequential Objects with Periodicity for Dynamic Information DisseminationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2008.14821:2(273-286)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1109/TKDE.2008.148
Chung YChen CLee C(2006)Design and Performance Evaluation of Broadcast Algorithms for Time-Constrained Data RetrievalIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2006.17118:11(1526-1543)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1109/TKDE.2006.171
Chih-Lin Hu Ming-Syan Chen (2005)On-line scheduling sequential objects for dynamic information disseminationGLOBECOM '05. IEEE Global Telecommunications Conference, 2005.10.1109/GLOCOM.2005.1577362(5 pp.)Online publication date: 2005
https://doi.org/10.1109/GLOCOM.2005.1577362
Hsu CLee GChen A(2005)An Efficient Algorithm for Near Optimal Data Allocation on Multiple Broadcast ChannelsDistributed and Parallel Databases10.1007/s10619-005-4949-918:3(207-222)Online publication date: 1-Nov-2005
https://dl.acm.org/doi/10.1007/s10619-005-4949-9
Naor JSchwartz RMunro I(2004)The directed circular arrangement problemProceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/982792.982804(86-95)Online publication date: 11-Jan-2004
https://dl.acm.org/doi/10.5555/982792.982804
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Pushing dependent data in clients-providers-servers systems

A Parallel Hill Climbing Algorithm for Pushing Dependent Data in Clients-Providers-Servers Systems

A parallel hill climbing algorithm for pushing dependent data in clients-providers-servers systems