{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/46692"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/46692","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Scheduling with privacy constraints","abstract":"Traditionally, scheduling policies have been optimized to perform well on metrics such as throughput, delay, and fairness. In the context of shared event schedulers, where a common processor is shared among multiple users, one also has to consider the associated privacy which is a measure of the information about the usage pattern of one user of the system that can be learned by another as a consequence of sharing the scheduler. Consider two processes, one of them an innocuous process (referred to as Alice) and the other a malicious one (referred to as Bob), using a common scheduler to process their jobs. Based on when his jobs get processed, Bob wishes to learn about the pattern (size and timing) of jobs of Alice. Depending on the context, knowledge of this pattern could have serious implications on Alice's privacy and security. For instance, shared routers can reveal traffic patterns, shared memory access can reveal cloud usage patterns, and so on. We present a formal framework to study the information leakage in shared resource schedulers. The first-come-first-serve (FCFS) scheduling policy and time-division-multiple-access (TDMA) are identified as two extreme policies on the privacy metric, FCFS has the least, and TDMA has the highest. However, on performance based metrics, such as throughput and delay, it is well known that FCFS significantly outperforms TDMA. This raises the question: \\emph{Is a tradeoff between delay and privacy fundamental to the design to scheduling policies? In particular, is there a work-conserving (a class of policies that offer minimal delay), possibly randomized, scheduling policy that scores high on the privacy metric?} Answering the first question, we show that there does exist a fundamental limit on the privacy performance of a work-conserving scheduling policy. We quantify this limit. Furthermore, answering the second question, we demonstrate that the round-robin scheduling policy (a deterministic policy) is privacy optimal within the class of work-conserving policies. We then derive two parametrized policies, accumulate and serve, and proportional TDMA, which take two different approaches to offer a tunable tradeoff between privacy and performance.","abstract_html":"Traditionally, scheduling policies have been optimized to perform well on metrics such as throughput, delay, and fairness. In the context of shared event schedulers, where a common processor is shared among multiple users, one also has to consider the associated privacy which is a measure of the information about the usage pattern of one user of the system that can be learned by another as a consequence of sharing the scheduler. Consider two processes, one of them an innocuous process (referred to as Alice) and the other a malicious one (referred to as Bob), using a common scheduler to process their jobs. Based on when his jobs get processed, Bob wishes to learn about the pattern (size and timing) of jobs of Alice. Depending on the context, knowledge of this pattern could have serious implications on Alice's privacy and security. For instance, shared routers can reveal traffic patterns, shared memory access can reveal cloud usage patterns, and so on. We present a formal framework to study the information leakage in shared resource schedulers. The first-come-first-serve (FCFS) scheduling policy and time-division-multiple-access (TDMA) are identified as two extreme policies on the privacy metric, FCFS has the least, and TDMA has the highest. However, on performance based metrics, such as throughput and delay, it is well known that FCFS significantly outperforms TDMA. This raises the question: \\emph{Is a tradeoff between delay and privacy fundamental to the design to scheduling policies? In particular, is there a work-conserving (a class of policies that offer minimal delay), possibly randomized, scheduling policy that scores high on the privacy metric?} Answering the first question, we show that there does exist a fundamental limit on the privacy performance of a work-conserving scheduling policy. We quantify this limit. Furthermore, answering the second question, we demonstrate that the round-robin scheduling policy (a deterministic policy) is privacy optimal within the class of work-conserving policies. We then derive two parametrized policies, accumulate and serve, and proportional TDMA, which take two different approaches to offer a tunable tradeoff between privacy and performance.","abstract_has_math":false,"creators":["Kadloor, Sachin"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Kiyavash, Negar","Hajek, Bruce","Srikant, Rayadurgam","Borisov, Nikita"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-01-16T17:59:14Z","date_published":"2014-01-16T17:59:14Z","updated_at":"2026-07-22T22:25:36Z","subjects":["scheduling","privacy","timing channel","side channel"],"languages":["en"],"rights":["Copyright 2013 Sachin Kadloor"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/46692","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kiyavash, Negar","Hajek, Bruce","Srikant, Rayadurgam","Borisov, Nikita"]},{"key":"dc:creator","label":"Author","values":["Kadloor, Sachin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-01-16T17:59:14Z","2013-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["scheduling","privacy","timing channel","side channel"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Sachin Kadloor"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/46692"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Traditionally, scheduling policies have been optimized to perform well on metrics such as throughput, delay, and fairness. In the context of shared event schedulers, where a common processor is shared among multiple users, one also has to consider the associated privacy which is a measure of the information about the usage pattern of one user of the system that can be learned by another as a consequence of sharing the scheduler. Consider two processes, one of them an innocuous process (referred to as Alice) and the other a malicious one (referred to as Bob), using a common scheduler to process their jobs. Based on when his jobs get processed, Bob wishes to learn about the pattern (size and timing) of jobs of Alice. Depending on the context, knowledge of this pattern could have serious implications on Alice's privacy and security. For instance, shared routers can reveal traffic patterns, shared memory access can reveal cloud usage patterns, and so on. We present a formal framework to study the information leakage in shared resource schedulers. The first-come-first-serve (FCFS) scheduling policy and time-division-multiple-access (TDMA) are identified as two extreme policies on the privacy metric, FCFS has the least, and TDMA has the highest. However, on performance based metrics, such as throughput and delay, it is well known that FCFS significantly outperforms TDMA. This raises the question: \\emph{Is a tradeoff between delay and privacy fundamental to the design to scheduling policies? In particular, is there a work-conserving (a class of policies that offer minimal delay), possibly randomized, scheduling policy that scores high on the privacy metric?} Answering the first question, we show that there does exist a fundamental limit on the privacy performance of a work-conserving scheduling policy. We quantify this limit. Furthermore, answering the second question, we demonstrate that the round-robin scheduling policy (a deterministic policy) is privacy optimal within the class of work-conserving policies. We then derive two parametrized policies, accumulate and serve, and proportional TDMA, which take two different approaches to offer a tunable tradeoff between privacy and performance.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-09-13T19:49:40Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 16 uiuc_thesis.tex: 8466 bytes, checksum: b5e6e5f65616d6a8706295af9c109498 (MD5) abs.tex: 2226 bytes, checksum: a6553a9de971cfd41139882a7195ef24 (MD5) intro.tex: 16143 bytes, checksum: 31c2fa134153bc18b9fbe69e6d732764 (MD5) ack.tex: 9640 bytes, checksum: f0338cded6551c3bcc72974aaa847589 (MD5) conc.tex: 24180 bytes, checksum: 6024ea655eddb5e067242b221083165a (MD5) tworouter.tex: 32001 bytes, checksum: bced3bc3072765f3808b3145d070ba1a (MD5) delays.tex: 10008 bytes, checksum: 8b679b42b10e45e21858f13631c7c80f (MD5) goodpolicies.tex: 19526 bytes, checksum: c0728f80899bc7be21f84172fdad88e2 (MD5) nonidling.tex: 78444 bytes, checksum: f452ccd975c284611d2f979f39fa1943 (MD5) fcfstdma.tex: 12438 bytes, checksum: 073826733b0954561ad701d26ddd2c3b (MD5) sysmodel.tex: 9257 bytes, checksum: 3a641559f1bddfdf8799c3d9f5c89159 (MD5) litsurvey.tex: 21725 bytes, checksum: 89cd5c55dd3a59ce20b39b3174d8d5ad (MD5) intro.tex: 16143 bytes, checksum: 31c2fa134153bc18b9fbe69e6d732764 (MD5) abs.tex: 2226 bytes, checksum: a6553a9de971cfd41139882a7195ef24 (MD5) uiuc_thesis.tex: 8466 bytes, checksum: b5e6e5f65616d6a8706295af9c109498 (MD5) Kadloor_Sachin.pdf: 1663048 bytes, checksum: 679edab2016a9efe88e5dbba8c4ffedb (MD5)","Made available in DSpace on 2014-01-16T17:59:14Z (GMT). No. of bitstreams: 17 Sachin_Kadloor.pdf: 1663048 bytes, checksum: 679edab2016a9efe88e5dbba8c4ffedb (MD5) uiuc_thesis.tex: 8466 bytes, checksum: b5e6e5f65616d6a8706295af9c109498 (MD5) abs.tex: 2226 bytes, checksum: a6553a9de971cfd41139882a7195ef24 (MD5) intro.tex: 16143 bytes, checksum: 31c2fa134153bc18b9fbe69e6d732764 (MD5) ack.tex: 9640 bytes, checksum: f0338cded6551c3bcc72974aaa847589 (MD5) conc.tex: 24180 bytes, checksum: 6024ea655eddb5e067242b221083165a (MD5) tworouter.tex: 32001 bytes, checksum: bced3bc3072765f3808b3145d070ba1a (MD5) delays.tex: 10008 bytes, checksum: 8b679b42b10e45e21858f13631c7c80f (MD5) goodpolicies.tex: 19526 bytes, checksum: c0728f80899bc7be21f84172fdad88e2 (MD5) nonidling.tex: 78444 bytes, checksum: f452ccd975c284611d2f979f39fa1943 (MD5) fcfstdma.tex: 12438 bytes, checksum: 073826733b0954561ad701d26ddd2c3b (MD5) sysmodel.tex: 9257 bytes, checksum: 3a641559f1bddfdf8799c3d9f5c89159 (MD5) litsurvey.tex: 21725 bytes, checksum: 89cd5c55dd3a59ce20b39b3174d8d5ad (MD5) 1_intro.tex: 16143 bytes, checksum: 31c2fa134153bc18b9fbe69e6d732764 (MD5) 1_abs.tex: 2226 bytes, checksum: a6553a9de971cfd41139882a7195ef24 (MD5) 1_uiuc_thesis.tex: 8466 bytes, checksum: b5e6e5f65616d6a8706295af9c109498 (MD5) license.txt: 4064 bytes, checksum: 08eb19bc681d47714d39948d88f5ad44 (MD5)"]},{"key":"dc:title","label":"Title","values":["Scheduling with privacy constraints"]}]}],"canonical_facts":{"dc:contributor":["Kiyavash, Negar","Hajek, Bruce","Srikant, Rayadurgam","Borisov, Nikita"],"dc:creator":["Kadloor, Sachin"],"dc:date":["2014-01-16T17:59:14Z","2013-12"],"dc:description":["Traditionally, scheduling policies have been optimized to perform well on metrics such as throughput, delay, and fairness. In the context of shared event schedulers, where a common processor is shared among multiple users, one also has to consider the associated privacy which is a measure of the information about the usage pattern of one user of the system that can be learned by another as a consequence of sharing the scheduler. Consider two processes, one of them an innocuous process (referred to as Alice) and the other a malicious one (referred to as Bob), using a common scheduler to process their jobs. Based on when his jobs get processed, Bob wishes to learn about the pattern (size and timing) of jobs of Alice. Depending on the context, knowledge of this pattern could have serious implications on Alice's privacy and security. For instance, shared routers can reveal traffic patterns, shared memory access can reveal cloud usage patterns, and so on. We present a formal framework to study the information leakage in shared resource schedulers. The first-come-first-serve (FCFS) scheduling policy and time-division-multiple-access (TDMA) are identified as two extreme policies on the privacy metric, FCFS has the least, and TDMA has the highest. However, on performance based metrics, such as throughput and delay, it is well known that FCFS significantly outperforms TDMA. This raises the question: \\emph{Is a tradeoff between delay and privacy fundamental to the design to scheduling policies? In particular, is there a work-conserving (a class of policies that offer minimal delay), possibly randomized, scheduling policy that scores high on the privacy metric?} Answering the first question, we show that there does exist a fundamental limit on the privacy performance of a work-conserving scheduling policy. We quantify this limit. Furthermore, answering the second question, we demonstrate that the round-robin scheduling policy (a deterministic policy) is privacy optimal within the class of work-conserving policies. We then derive two parametrized policies, accumulate and serve, and proportional TDMA, which take two different approaches to offer a tunable tradeoff between privacy and performance.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2013-09-13T19:49:40Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 16 uiuc_thesis.tex: 8466 bytes, checksum: b5e6e5f65616d6a8706295af9c109498 (MD5) abs.tex: 2226 bytes, checksum: a6553a9de971cfd41139882a7195ef24 (MD5) intro.tex: 16143 bytes, checksum: 31c2fa134153bc18b9fbe69e6d732764 (MD5) ack.tex: 9640 bytes, checksum: f0338cded6551c3bcc72974aaa847589 (MD5) conc.tex: 24180 bytes, checksum: 6024ea655eddb5e067242b221083165a (MD5) tworouter.tex: 32001 bytes, checksum: bced3bc3072765f3808b3145d070ba1a (MD5) delays.tex: 10008 bytes, checksum: 8b679b42b10e45e21858f13631c7c80f (MD5) goodpolicies.tex: 19526 bytes, checksum: c0728f80899bc7be21f84172fdad88e2 (MD5) nonidling.tex: 78444 bytes, checksum: f452ccd975c284611d2f979f39fa1943 (MD5) fcfstdma.tex: 12438 bytes, checksum: 073826733b0954561ad701d26ddd2c3b (MD5) sysmodel.tex: 9257 bytes, checksum: 3a641559f1bddfdf8799c3d9f5c89159 (MD5) litsurvey.tex: 21725 bytes, checksum: 89cd5c55dd3a59ce20b39b3174d8d5ad (MD5) intro.tex: 16143 bytes, checksum: 31c2fa134153bc18b9fbe69e6d732764 (MD5) abs.tex: 2226 bytes, checksum: a6553a9de971cfd41139882a7195ef24 (MD5) uiuc_thesis.tex: 8466 bytes, checksum: b5e6e5f65616d6a8706295af9c109498 (MD5) Kadloor_Sachin.pdf: 1663048 bytes, checksum: 679edab2016a9efe88e5dbba8c4ffedb (MD5)","Made available in DSpace on 2014-01-16T17:59:14Z (GMT). No. of bitstreams: 17 Sachin_Kadloor.pdf: 1663048 bytes, checksum: 679edab2016a9efe88e5dbba8c4ffedb (MD5) uiuc_thesis.tex: 8466 bytes, checksum: b5e6e5f65616d6a8706295af9c109498 (MD5) abs.tex: 2226 bytes, checksum: a6553a9de971cfd41139882a7195ef24 (MD5) intro.tex: 16143 bytes, checksum: 31c2fa134153bc18b9fbe69e6d732764 (MD5) ack.tex: 9640 bytes, checksum: f0338cded6551c3bcc72974aaa847589 (MD5) conc.tex: 24180 bytes, checksum: 6024ea655eddb5e067242b221083165a (MD5) tworouter.tex: 32001 bytes, checksum: bced3bc3072765f3808b3145d070ba1a (MD5) delays.tex: 10008 bytes, checksum: 8b679b42b10e45e21858f13631c7c80f (MD5) goodpolicies.tex: 19526 bytes, checksum: c0728f80899bc7be21f84172fdad88e2 (MD5) nonidling.tex: 78444 bytes, checksum: f452ccd975c284611d2f979f39fa1943 (MD5) fcfstdma.tex: 12438 bytes, checksum: 073826733b0954561ad701d26ddd2c3b (MD5) sysmodel.tex: 9257 bytes, checksum: 3a641559f1bddfdf8799c3d9f5c89159 (MD5) litsurvey.tex: 21725 bytes, checksum: 89cd5c55dd3a59ce20b39b3174d8d5ad (MD5) 1_intro.tex: 16143 bytes, checksum: 31c2fa134153bc18b9fbe69e6d732764 (MD5) 1_abs.tex: 2226 bytes, checksum: a6553a9de971cfd41139882a7195ef24 (MD5) 1_uiuc_thesis.tex: 8466 bytes, checksum: b5e6e5f65616d6a8706295af9c109498 (MD5) license.txt: 4064 bytes, checksum: 08eb19bc681d47714d39948d88f5ad44 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/46692"],"dc:language":["en"],"dc:rights":["Copyright 2013 Sachin Kadloor"],"dc:subject":["scheduling","privacy","timing channel","side channel"],"dc:title":["Scheduling with privacy constraints"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:36Z"}