Ontology type: schema:ScholarlyArticle
2018-11
AUTHORSHong-Liang Li, Jie Wu, Zhen Jiang, Xiang Li, Xiao-Hui Wei
ABSTRACTStream processing applications continuously process large amounts of online streaming data in real time or near real time. They have strict latency constraints. However, the continuous processing makes them vulnerable to any failures, and the recoveries may slow down the entire processing pipeline and break latency constraints. The upstream backup scheme is one of the most widely applied fault-tolerant schemes for stream processing systems. It introduces complex backup dependencies to tasks, which increases the difficulty of controlling recovery latencies. Moreover, when dependent tasks are located on the same processor, they fail at the same time in processor-level failures, bringing extra recovery latencies that increase the impacts of failures. This paper studies the relationship between the task allocation and the recovery latency of a stream processing application. We present a correlated failure effect model to describe the recovery latency of a stream topology in processor-level failures under a task allocation plan. We introduce a recovery-latency aware task allocation problem (RTAP) that seeks task allocation plans for stream topologies that will achieve guaranteed recovery latencies. We discuss the difference between RTAP and classic task allocation problems and present a heuristic algorithm with a computational complexity of O(n log2n) to solve the problem. Extensive experiments were conducted to verify the correctness and effectiveness of our approach. It improves the resource usage by 15%–20% on average. More... »
PAGES1125-1139
http://scigraph.springernature.com/pub.10.1007/s11390-018-1876-6
DOIhttp://dx.doi.org/10.1007/s11390-018-1876-6
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1110033157
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Temple University",
"id": "https://www.grid.ac/institutes/grid.264727.2",
"name": [
"College of Computer Science and Technology, Jilin University, 130012, Changchun, China",
"Key Laboratory of Symbolic Computation and Knowledge Engineering of the Ministry of Education, 130012, Changchun, China",
"Department of Computer and Information Sciences, Temple University, 19122, Philadelphia, PA, U.S.A."
],
"type": "Organization"
},
"familyName": "Li",
"givenName": "Hong-Liang",
"type": "Person"
},
{
"affiliation": {
"alternateName": "Temple University",
"id": "https://www.grid.ac/institutes/grid.264727.2",
"name": [
"Department of Computer and Information Sciences, Temple University, 19122, Philadelphia, PA, U.S.A."
],
"type": "Organization"
},
"familyName": "Wu",
"givenName": "Jie",
"type": "Person"
},
{
"affiliation": {
"alternateName": "West Chester University",
"id": "https://www.grid.ac/institutes/grid.268132.c",
"name": [
"Department of Computer Science, West Chester University of Pennsylvania, 19383, West Chester, PA, U.S.A."
],
"type": "Organization"
},
"familyName": "Jiang",
"givenName": "Zhen",
"id": "sg:person.014746007677.81",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014746007677.81"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Jilin University",
"id": "https://www.grid.ac/institutes/grid.64924.3d",
"name": [
"College of Computer Science and Technology, Jilin University, 130012, Changchun, China"
],
"type": "Organization"
},
"familyName": "Li",
"givenName": "Xiang",
"type": "Person"
},
{
"affiliation": {
"alternateName": "Jilin University",
"id": "https://www.grid.ac/institutes/grid.64924.3d",
"name": [
"College of Computer Science and Technology, Jilin University, 130012, Changchun, China",
"Key Laboratory of Symbolic Computation and Knowledge Engineering of the Ministry of Education, 130012, Changchun, China"
],
"type": "Organization"
},
"familyName": "Wei",
"givenName": "Xiao-Hui",
"type": "Person"
}
],
"citation": [
{
"id": "https://doi.org/10.1145/1989323.1989350",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1000975391"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0022-0000(74)80044-9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1000999206"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/872757.872789",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001262233"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2463676.2465272",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1001474693"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2674026.2674028",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1003320822"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2588555.2595641",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011686270"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2661829.2661882",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1011754334"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.cosrev.2016.12.001",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013347914"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2723372.2742788",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1013804236"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2465351.2465353",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015991543"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2933267.2933312",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017457549"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.jss.2016.08.037",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1018598520"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/872757.872857",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1019022800"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/800152.804907",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1024017488"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/1107499.1107504",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1029230064"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0377-2217(02)00123-6",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1030478254"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2723372.2749437",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032270790"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/872757.872854",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1036451105"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/1999995.2000008",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037341469"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/1331904.1331907",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039080811"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/361147.361115",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041460956"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/j.jcss.2016.10.010",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1043435972"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-1-4419-7997-1_35",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047658800",
"https://doi.org/10.1007/978-1-4419-7997-1_35"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2463676.2465282",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047707600"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/2675743.2771831",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1053737749"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/12.588063",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061088605"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tbdata.2016.2638860",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061523341"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tkde.2007.1056",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061661662"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/0603007",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062848732"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1287/ijoc.1120.0499",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1064706949"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.14778/2536222.2536229",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1067368174"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10586-017-0870-z",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1085075631",
"https://doi.org/10.1007/s10586-017-0870-z"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10586-017-0870-z",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1085075631",
"https://doi.org/10.1007/s10586-017-0870-z"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.3837/tiis.2017.04.008",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1085521885"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/tr.2017.2712563",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1087303136"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10586-017-1011-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1090325524",
"https://doi.org/10.1007/s10586-017-1011-4"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/s10586-017-1011-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1090325524",
"https://doi.org/10.1007/s10586-017-1011-4"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/icdcs.2015.48",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1093251716"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/icpads.2015.106",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1094120693"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/icdmw.2010.172",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1094212263"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/icde.2016.7498267",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1094596428"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/cluster.2017.10",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095218809"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/infocom.2016.7524433",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095389335"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/icde.2005.72",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1095475136"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/pccc.2017.8280443",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1100848492"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/icccn.2018.8487327",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1107558425"
],
"type": "CreativeWork"
}
],
"datePublished": "2018-11",
"datePublishedReg": "2018-11-01",
"description": "Stream processing applications continuously process large amounts of online streaming data in real time or near real time. They have strict latency constraints. However, the continuous processing makes them vulnerable to any failures, and the recoveries may slow down the entire processing pipeline and break latency constraints. The upstream backup scheme is one of the most widely applied fault-tolerant schemes for stream processing systems. It introduces complex backup dependencies to tasks, which increases the difficulty of controlling recovery latencies. Moreover, when dependent tasks are located on the same processor, they fail at the same time in processor-level failures, bringing extra recovery latencies that increase the impacts of failures. This paper studies the relationship between the task allocation and the recovery latency of a stream processing application. We present a correlated failure effect model to describe the recovery latency of a stream topology in processor-level failures under a task allocation plan. We introduce a recovery-latency aware task allocation problem (RTAP) that seeks task allocation plans for stream topologies that will achieve guaranteed recovery latencies. We discuss the difference between RTAP and classic task allocation problems and present a heuristic algorithm with a computational complexity of O(n log2n) to solve the problem. Extensive experiments were conducted to verify the correctness and effectiveness of our approach. It improves the resource usage by 15%\u201320% on average.",
"genre": "research_article",
"id": "sg:pub.10.1007/s11390-018-1876-6",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1320078",
"issn": [
"1666-6046",
"1666-6038"
],
"name": "Journal of Computer Science and Technology",
"type": "Periodical"
},
{
"issueNumber": "6",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "33"
}
],
"name": "A Task Allocation Method for Stream Processing with Recovery Latency Constraint",
"pagination": "1125-1139",
"productId": [
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"8491f4648ed917ba419c42f2e702d33f49abfdf1a1a409fe9b41f3f79932d070"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s11390-018-1876-6"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1110033157"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s11390-018-1876-6",
"https://app.dimensions.ai/details/publication/pub.1110033157"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T08:09",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000267_0000000267/records_56093_00000000.jsonl",
"type": "ScholarlyArticle",
"url": "https://link.springer.com/10.1007%2Fs11390-018-1876-6"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s11390-018-1876-6'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s11390-018-1876-6'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11390-018-1876-6'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11390-018-1876-6'
This table displays all metadata directly associated to this object as RDF triples.
229 TRIPLES
21 PREDICATES
71 URIs
19 LITERALS
7 BLANK NODES