2017/05/24 by Asa Dan, Dan, Asa, Rajit Manohar +3
Computer Science · Engineering · #Advanced Memory and Neural Computing #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1705.08627
openalex publication_date 2017/05/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Even in the absence of clocks, time bounds on the duration of actions enable the use of time for distributed coordination. This paper initiates an investigation of coordination in such a setting. A new communication structure called a zigzag pattern is introduced, and shown to guarantee bounds on the relative timing of events in this clockless model. Indeed, zigzag patterns are shown to be necessary and sufficient for establishing that events occur in a manner that satisfies prescribed bounds. We capture when a process can know that an appropriate zigzag pattern exists, and use this to provide necessary and sufficient conditions for timed coordination of events using a full-information protocol in the clockless model.