Wait-Free Approximate Agreement on Graphs
العنوان: | Wait-Free Approximate Agreement on Graphs |
---|---|
المؤلفون: | Faith Ellen, Dan Alistarh, Joel Rybicki |
المصدر: | Structural Information and Communication Complexity ISBN: 9783030795269 SIROCCO |
بيانات النشر: | Springer International Publishing, 2021. |
سنة النشر: | 2021 |
مصطلحات موضوعية: | Discrete mathematics, Vertex (graph theory), Shared memory, Asynchronous communication, Computer science, Reading (computer), media_common.quotation_subject, Shortest path problem, Process (computing), Value (computer science), Agreement, MathematicsofComputing_DISCRETEMATHEMATICS, media_common |
الوصف: | 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 all the outputs are within distance 1 of one another, and each output value lies on a shortest path between two input values. |
ردمك: | 978-3-030-79526-9 |
URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::408659c9fb22735c0ac80f67f2053d1b https://doi.org/10.1007/978-3-030-79527-6_6 |
حقوق: | OPEN |
رقم الأكسشن: | edsair.doi...........408659c9fb22735c0ac80f67f2053d1b |
قاعدة البيانات: | OpenAIRE |
ردمك: | 9783030795269 |
---|