[{"status":"public","conference":{"location":"Wrocław, Poland","end_date":"2021-07-01","start_date":"2021-06-28","name":"SIROCCO: Structural Information and Communication Complexity"},"type":"conference","_id":"9823","department":[{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"DaAl"}],"creator":{"id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","login":"asandaue"},"date_updated":"2023-02-23T14:09:49Z","intvolume":" 12810","month":"06","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2103.08949"}],"scopus_import":"1","alternative_title":[],"oa_version":"Preprint","abstract":[{"lang":"eng"}],"volume":12810,"language":[{}],"publication_status":"published","publication_identifier":{"isbn":[],"eissn":[],"issn":[]},"external_id":{"arxiv":[]},"article_processing_charge":"No","author":[{"orcid":"0000-0003-3650-940X","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian"},{"last_name":"Ellen","first_name":"Faith"},{"last_name":"Rybicki","orcid":"0000-0002-6432-6646","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","first_name":"Joel"}],"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","citation":{"mla":"Alistarh, Dan-Adrian, et al. “Wait-Free Approximate Agreement on Graphs.” Structural Information and Communication Complexity, vol. 12810, Springer Nature, 2021, pp. 87–105, doi:10.1007/978-3-030-79527-6_6.","short":"D.-A. Alistarh, F. Ellen, J. Rybicki, in:, Structural Information and Communication Complexity, Springer Nature, 2021, pp. 87–105.","ieee":"D.-A. Alistarh, F. Ellen, and J. Rybicki, “Wait-free approximate agreement on graphs,” in Structural Information and Communication Complexity, Wrocław, Poland, 2021, vol. 12810, pp. 87–105.","apa":"Alistarh, D.-A., Ellen, F., & Rybicki, J. (2021). Wait-free approximate agreement on graphs. In Structural Information and Communication Complexity (Vol. 12810, pp. 87–105). Wrocław, Poland: Springer Nature. https://doi.org/10.1007/978-3-030-79527-6_6","chicago":"Alistarh, Dan-Adrian, Faith Ellen, and Joel Rybicki. “Wait-Free Approximate Agreement on Graphs.” In Structural Information and Communication Complexity, 12810:87–105. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-79527-6_6.","ista":"Alistarh D-A, Ellen F, Rybicki J. 2021. Wait-free approximate agreement on graphs. Structural Information and Communication Complexity. SIROCCO: Structural Information and Communication Complexity, LNCS, vol. 12810, 87–105."},"dini_type":"doc-type:conferenceObject","oa":1,"quality_controlled":"1","date_created":"2021-08-08T22:01:29Z","date_published":"2021-06-20T00:00:00Z","page":"87-105","uri_base":"https://research-explorer.ista.ac.at","publication":"Structural Information and Communication Complexity","dc":{"creator":["Alistarh, Dan-Adrian","Ellen, Faith","Rybicki, Joel"],"language":["eng"],"rights":["info:eu-repo/semantics/openAccess"],"title":["Wait-free approximate agreement on graphs","LNCS"],"description":["Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to shared memory. In this work, we consider a natural generalisation of approximate agreement on arbitrary undirected connected graphs. Each process is given a vertex of the graph as input and, if non-faulty, must output a vertex such that\r\nall the outputs are within distance 1 of one another, and\r\n\r\neach output value lies on a shortest path between two input values.\r\n\r\nFrom prior work, it is known that there is no wait-free algorithm among 𝑛≥3 processes for this problem on any cycle of length 𝑐≥4 , by reduction from 2-set agreement (Castañeda et al. 2018).\r\n\r\nIn this work, we investigate the solvability and complexity of this task on general graphs. We give a new, direct proof of the impossibility of approximate agreement on cycles of length 𝑐≥4 , via a generalisation of Sperner’s Lemma to convex polygons. We also extend the reduction from 2-set agreement to a larger class of graphs, showing that approximate agreement on these graphs is unsolvable. On the positive side, we present a wait-free algorithm for a class of graphs that properly contains the class of chordal graphs."],"identifier":["https://research-explorer.ista.ac.at/record/9823"],"source":["Alistarh D-A, Ellen F, Rybicki J. Wait-free approximate agreement on graphs. In: Structural Information and Communication Complexity. Vol 12810. Springer Nature; 2021:87-105. doi:10.1007/978-3-030-79527-6_6"],"relation":["info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-030-79527-6_6","info:eu-repo/semantics/altIdentifier/issn/03029743","info:eu-repo/semantics/altIdentifier/issn/16113349","info:eu-repo/semantics/altIdentifier/isbn/9783030795269","info:eu-repo/semantics/altIdentifier/arxiv/2103.08949"],"publisher":["Springer Nature"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"date":["2021"]},"day":"20"}]